HDU-3065 病毒侵袭持续中

思路:
AC自动机模板题，最后拓扑优化即可，存下每个单词结尾的编号，通过编号找出它是否被遍历过。
注意:该题是多组案例。

实现:

#include <stdio.h>
#include <string.h>
const int N = 2e6 + 5, M = 50005;
int tr[M][26], idx = 1, nex[M], q[M], id[M], f[M];
char s[N];
char t[1005][55];
void insert(char s[], int x)
{
    int p = 0;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
    {
        int t = s[i] - 'A';
        if (!tr[p][t])
            tr[p][t] = idx++;
        p = tr[p][t];
    }
    id[x] = p;
}
void build()
{
    int hh = 1, tt = 0;
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q[++tt] = tr[0][i];
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = 0; i < 26; i++)
        {
            int &p = tr[t][i];
            if (!p)
                p = tr[nex[t]][i];
            else
            {
                nex[p] = tr[nex[t]][i];
                q[++tt] = p;
            }
        }
    }
}
int main()
{

    int n;
    while (scanf("%d", &n) != EOF)
    {
        memset(tr, 0, sizeof tr);
        memset(nex, 0, sizeof nex);
        memset(f, 0, sizeof f);
        idx = 1;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", t[i] + 1);
            insert(t[i], i);
        }
        build();
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int i = 1, j = 0; i <= len; i++)
        {
            int t = s[i] - 'A';
            if (t < 0 || t > 25)
            {
                j = 0;
                continue;
            }
            j = tr[j][t];
            f[j]++;
        }
        for (int i = idx - 1; i >= 1; i--)
            f[nex[q[i]]] += f[q[i]];
        for (int i = 1; i <= n; i++)
        {
            if (f[id[i]])
            {
                int len = strlen(t[i] + 1);
                for (int j = 1; j <= len; j++)
                    printf("%c", t[i][j]);
                printf(": ");
                printf("%d\n", f[id[i]]);
            }
        }
    }
    return 0;
}