lightoj 1427 - Substring Frequency (II) AC自动机

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cmath>
#include<climits>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define pb(a) push(a)
#define INF 0x1f1f1f1f
#define lson idx<<1,l,mid
#define rson idx<<1|1,mid+1,r
#define PI  3.1415926535898
template<class T> T min(const T& a, const T& b, const T& c)
{
    return min(min(a, b), c);
}
template<class T> T max(const T& a, const T& b, const T& c)
{
    return max(max(a, b), c);
}
void debug()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt","r",stdin);
    // freopen("d:\\out1.txt","w",stdout);
#endif
}
int getch()
{
    int ch;
    while((ch = getchar()) != EOF)
    {
        if(ch!=‘ ‘ && ch!=‘\n‘) return ch;
    }
    return EOF;
}

const int max_len = 510;
const int max_node = max_len * max_len;
const int sigma_size = 26;

struct ac_automation
{
    int sz;
    int ch[max_node][sigma_size];
    int fail[max_node];
    vector<int> val[max_node];
    int last[max_node];

    void init()
    {
        memset(ch[0], 0, sizeof(ch[0]));
        val[0].clear();
        sz = 1;
    }
    int id(char c)
    {
        return c - ‘a‘;
    }
    void insert(const char *s, int v)
    {
        int u = 0;
        for(int i = 0; s[i] != ‘\0‘; i++)
        {
            int v = id(s[i]);
            if(!ch[u][v])
            {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz].clear();
                ch[u][v] = sz++;
            }
            u = ch[u][v];
        }
        val[u].push_back(v);
    }

    void construct()
    {
        queue<int> q;
        fail[0] = 0;
        for(int c = 0; c < sigma_size; c++)
        {
            int u = ch[0][c];
            if(u) {q.push(u); fail[u] = 0; last[u] = 0; }
        }

        while(!q.empty())
        {
            int r = q.front(); q.pop();
            for(int c = 0; c < sigma_size; c++)
            {
                int u = ch[r][c];
                if(u)
                {
                    q.push(u);
                    fail[u] = ch[fail[r]][c];
                    last[u] = (!val[fail[u]].empty()) ? fail[u] : last[fail[u]];
                } else ch[r][c] = ch[fail[r]][c];
            }
        }
    }

    void count(int x[], int u)
    {
        if(val[u].size() > 0)
        {
            for(int i = 0; i < val[u].size(); i++)
                x[val[u][i]]++;
            count(x, last[u]);
        }
    }
    void find(const char *T, int x[])
    {
        int u = 0;
        for(int i = 0; T[i] != ‘\0‘; i++)
        {
            int v = id(T[i]);
            u = ch[u][v];
            if(!val[u].empty()) count(x, u);
            else if(last[u]) count(x, last[u]);
        }
    }
};


ac_automation solver;
const int maxn = 1000100;
char T[maxn];
int ans[maxn];

int main()
{
    debug();
    int t;
    scanf("%d", &t);
    for(int ca = 1; ca <= t; ca++)
    {
        solver.init();
        int n;
        scanf("%d%s", &n, T);
        for(int i = 1; i <= n; i++)
        {
            char word[max_len];
            scanf("%s", word);
            solver.insert(word, i);
        }
        solver.construct();

        memset(ans, 0, sizeof(ans));
        solver.find(T, ans);

        printf("Case %d:\n", ca);
        for(int i = 1; i <= n; i++)
        {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}