HDU - 2222 Keywords Search

思路:
AC自动机模板+拓扑优化。
因为当前单词可能包含别的单词，所以需要一直nex,但是本题会超时，所以思考优化这个过程。
我们知道，拓扑优化，可以将所有出现过的字符都标记上，这样的话，我们直接记录下，每个单词结尾的编号，最后看每个单词，结尾编号是否有标记，有标记则表示该单词存在文章中。

实现:

#include <algorithm>
#include <stdio.h>
#include <map>
#include <cstring>
using namespace std;

const int N = 10005, S = 51, M = 1000010;
// tr就是多个模式串构造的fail指针
// cnt标记该位置上有无单词
// id[i]:第i个模式串结尾所在的下标
int tr[N * S][26], idx = 1, nex[N * S], q[N * S], cnt[N * S], id[N], f[N * S];
char s[M];

void insert(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];
    }
    cnt[p]++;
    id[x] = p;
}

/*
 *	作用:构造多个模式串nex数组即fail树
 *	时间复杂度:O(插入的字符的总长度)
 */
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 _;
    scanf("%d", &_);
    while (_--)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(nex, 0, sizeof nex);
        memset(f, 0, sizeof f);
        int n;
        scanf("%d", &n);
        idx = 1;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s + 1);
            insert(i);
        }
        int res = 0;
        build();
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int i = 1, j = 0; i <= len; i++)
        {
            int t = s[i] - 'a';
            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]])
                res++;
        printf("%d\n", res);
    }

    return 0;
}