HDU - 2896 病毒侵袭

思路:
AC自动机模板题，最后拓扑优化即可。
注意：该题行末有空格会PE。该题是所有ASCII值，所以遍历的时候不能遍历到26,取字母的时候不能 -'a'
实现:

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 10005, M = 100005, F = 129;
int tr[M][130], idx = 1, nex[M], q[M], id[M], f[M];
char s[N];
void insert(char s[], int x)
{
    int p = 0;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
    {
        int t = (int)s[i];
        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 < F; i++)
        if (tr[0][i])
            q[++tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = 0; i < F; 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;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        insert(s, i);
    }
    build();

    int m;
    scanf("%d", &m);
    int tot = 0;
    for (int hh = 1; hh <= m; hh++)
    {
        memset(f, 0, sizeof f);
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int i = 1, j = 0; i <= len; i++)
        {
            int t = (int)s[i];
            j = tr[j][t];
            f[j]++;
        }
        for (int i = idx - 1; i >= 1; i--)
            f[nex[q[i]]] += f[q[i]];

        int flag = 0;
        for (int i = 1; i <= n; i++)
        {
            if (f[id[i]])
            {
                if (!flag)
                    printf("web %d:", hh);
                printf(" %d", i);
                flag = 1;
            }
        }
        tot += flag;
        if (flag)
            printf("\n");
    }
    printf("total: %d\n", tot);

    return 0;
}