aho_corasick

#define ma 500*500
int f[505];
///***********//////////////////////////////////
struct state {
    int to[26] ;
    int depth ;
    int suffLink ;
    int par ;
    int parLet ;
    int cnt ;
    int nxt[26] ;
};
vector <int> g[ma+500] ;
state states[ma+500];
int totNodes;
inline int add (string &str,ll x) {
    int cur = 1 ; // root with a empty string
    int len = str.size() ;
    for (int i = 0 ; i < len ; i++) {
        char c = str[i] ;
        if (!states[cur].to[c-'a']) {
            states[cur].to[c-'a'] = ++totNodes ;
            states[totNodes].par = cur ;
            states[totNodes].depth = states[cur].depth + 1 ;
            states[totNodes].parLet = c-'a' ;
        }
        cur = states[cur].to[c-'a'] ;
    }
    states[cur].cnt++;
    f[x]=cur;
    return cur ;
}
void pushLinks() {
    queue <int> Q ; Q.push(1) ;
    while (!Q.empty()) {
        int node = Q.front() ;
        Q.pop() ;
        if (states[node].depth <= 1) {
            states[node].suffLink = 1 ;
        }
        else {
            int cur = states[states[node].par].suffLink ;
            int parLet = states[node].parLet ;
            while (cur > 1 and !states[cur].to[parLet]) {
                cur = states[cur].suffLink ;
            }
            if (states[cur].to[parLet]) {
                cur = states[cur].to[parLet] ;
            }
            states[node].suffLink = cur ;
        }
        if (node != 1) g[states[node].suffLink].push_back(node) ;
        for (int i = 0 ; i < 26 ; i++) {
            if (states[node].to[i]) {
                Q.push(states[node].to[i]) ;
            }
        }
    }
}
void dfs (int u , int p) {
    if(p != -1) states[u].cnt += states[p].cnt;
    for (int i = 0 ; i < g[u].size() ; i++) {
        int v = g[u][i] ;
        if (v == p) continue ;
        dfs(v,u) ;
    }
}
int Next (int from , char ch) {
    if (states[from].nxt[ch-'a']) return states[from].nxt[ch-'a'] ;
    int cur = from ;
    int c = ch - 'a' ;
    while (cur > 1 and !states[cur].to[c]) {
        cur = states[cur].suffLink ;
    }
    if (states[cur].to[c]) {
        cur = states[cur].to[c] ;
    }
    return states[from].nxt[ch-'a'] = cur;
}

/////****************//////////////////////
string t[505];
int dp[ma+500];
void dfs2(ll u,ll par)
{
 ll i;
 for(i=0;i<g[u].sz;i++)
 {
  ll p=g[u][i];
  if(p==par)continue;
  dfs2(p,u);
  dp[u]+=dp[p];
 }
}
void clea()
{
 memset(states,0,sizeof(states));
 for(ll i=0;i<=totNodes;i++)
 {
  dp[i]=0;
  g[i].clr;
 }

 totNodes=1;
}
int main()
{
 ll i,j,n,tc,cas=0;
 cin>>tc;
 while(tc--)
 {
 string t1;
 cin>>n;
 cin>>t1;
 totNodes=1;
 for(i=1;i<=n;i++)
 {
  cin>>t[i];
  add(t[i],i);
 }
 pushLinks();
 ll now=1;
 for(i=0;i<t1.sz;i++)
 {
  now=Next(now,t1[i]);
  dp[now]++;
 }
 dfs2(1,-1);
 pf("Case %lld:\n",++cas);
 for(i=1;i<=n;i++)cout<<dp[f[i]]<<endl;
 clea();
 }
}