strings - Aho-Corasick

/************************************************************************
 *                    Aho-corasick Implementation                        *
 *                                                                       *
 *  Given some dictionary and Text. Output The occurances of each
 dictionary in the Text in O(|T| + |S|)
 *   Memory : |S|
 *   Implementation :
 * Insert each dictionary in trie
 * Now scan through the text. If there is transition,then make,
 * or look for alternative by going to suffix link
 # to => transition, link => greatest suffix link
 * init()
 * insert()
 * fail()
 # The below code output the # of occurance of each dictionary
 **************************************************************************/
#include <bits/stdc++.h>
using namespace std;

const int N = 25e4+4;
const int SIGMA = 26;
int Map[505];
namespace Aho{
    int to[N][SIGMA], link[N] , go;
    int nc[N];
    vector<int>VQ;
    void init()
    {
        memset(link,0,sizeof link);
        memset(to,0,sizeof to);
        memset(nc,0,sizeof nc);
        VQ.clear();
        go = 1;
    }
    void insert(char s[],int k)
    {
        int cur = 0;
        for(int i= 0; s[i];i ++ ) {
            int c = s[i]-'a';
            if(!to[cur][c]){
                to[cur][c] = go ++;
            }
            cur = to[cur][c];
        }
        Map[k] = cur;
    }
    void fail()
    {
        queue<int>q;
        for(int c = 0 ; c< SIGMA; c ++) {
            if(to[0][c]) q.push(to[0][c]);
            else to[0][c] = 0;
        }
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int c = 0; c < SIGMA; c ++ ) {
                if(!to[u][c]) {
                    to[u][c]= to[link[u]][c];
                }
                else {
                    int v = to[u][c];
                    link[v] = to[link[u]][c];
                    q.push(v);
                    VQ.push_back(v);
                }
            }
        }
    }
    void find(char s[])
    {
        for(int i = 0, j = 0; s[i] ;  i ++ ) {
            int c = s[i]-'a';
            while(j>0&&!to[j][c]) j = link[j];
            if(to[j][c]) j = to[j][c];
            nc[j] ++;
        }
    }
    void calc()
    {
        reverse(VQ.begin(), VQ.end());
        for(int i = 0; i < VQ.size(); i ++ ) {
            nc[link[VQ[i]]] += nc[VQ[i]];
        }
    }

};
char T[1000006];
char s[505];

int main()
{
    int t,cs=0,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%s",T);
        Aho::init();
        memset(Map,0,sizeof Map);
        for(int i = 0; i < n; i ++ ){
            scanf("%s",s);
            Aho::insert(s,i);
        }
        Aho::fail();
        Aho::find(T);
        Aho::calc();
        printf("Case %d:\n",++cs);
        for(int i = 0; i < n ; i ++ ) printf("%d\n", Aho::nc[Map[i]]);
    }

}