学步园

公认的学习AC自动机的第一道练手题。还不懂AC自动机的可以看这里AC自动机

题意：输入n(n<=10000)个单词，单词长度<=50，再输入一个目标串（长度<=10^6）。问目标串中包含了多少个单词，单词出现多次时只算一次。

几组测试数据：

2
he
tea
teaheteahehe
2  //多次出现不重复计数

2
he
shes
shes
2  //可能出现单词相互包含的情况

//注意，数据中有单词相同的情况，相同的单词要当做是不同的来看。
3
he
he
he
hehehehehehehe
3

3
he
he
he
he
3  //一次就能匹配3个单词，把这3个he看错不同的单词就行了

所以，每组数据的答案，一定是不大于n的。因为一个单词只计数一次

我的代码：

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

class ACAutomaton
{
public:
    static const int MAX_N = 10000 * 50 + 5;   //最大结点数：模式串个数 X 模式串最大长度
    static const int CLD_NUM = 26;             //从每个结点出发的最多边数：本题是26个小写字母

    int n;                          //当前结点总数
    int id['z'+1];                  //字母x对应的结点编号为id[x]
    int fail[MAX_N];                //fail指针
    int cnt[MAX_N];                 //本题所需
    int trie[MAX_N][CLD_NUM];       //trie tree

    void init()
    {
        for (int i = 0; i < CLD_NUM; i++)
            id['a'+i] = i;
    }

    void reset()
    {
        memset(trie[0], -1, sizeof(trie[0]));
        cnt[0] = 0;
        n = 1;
    }

    //插入模式串s，构造单词树(keyword tree)
    void add(char *s)
    {
        int p = 0;
        while (*s)
        {
            int i = id[*s];
            if ( -1 == trie[p][i] )
            {
                memset(trie[n], -1, sizeof(trie[n]));
                cnt[n] = 0;
                trie[p][i] = n++;
            }
            p = trie[p][i];
            s++;
        }
        cnt[p]++;
    }

    //用BFS来计算每个结点的fail指针，构造trie树
    void construct()
    {
        queue<int> Q;
        fail[0] = 0;
        for (int i = 0; i < CLD_NUM; i++)
        {
            if (-1 != trie[0][i])
            {
                fail[trie[0][i]] = 0;
                Q.push(trie[0][i]);
            }
            else
            {
                trie[0][i] = 0;    //这个不能丢
            }
        }
        while ( !Q.empty() )
        {
            int u = Q.front();
            Q.pop();
            //cnt[u] += cnt[fail[u]];
            for (int i = 0; i < CLD_NUM; i++)
            {
                int &v = trie[u][i];
                if ( -1 != v )
                {
                    Q.push(v);
                    fail[v] = trie[fail[u]][i];
                }
                else
                {
                    v = trie[fail[u]][i];
                }
            }
        }
    }

    //因题而异
    //本题是计算在目标串t中出现模式串的次数（可以重叠）
    int solve(char *t)
    {
        int q = 0, ret = 0;
        while ( *t )
        {
            int i = id[*t];
            q = trie[q][i];
            int u = q;
            while ( u != 0 )
            {
                ret += cnt[u];
                cnt[u] = 0;     //这里是避免重复计数
                u = fail[u];
            }
            t++;
        }
        return ret;
    }
} AC;

char keyword[55];
char target[1000005];

int main()
{
    int t, n;

    AC.init();
    cin >> t;
    while (t--)
    {
        AC.reset();
        scanf("%d", &n);
        while (n--)
        {
            scanf("%s", keyword);
            AC.add(keyword);
        }
        AC.construct();

        scanf("%s", target);
        printf("%d\n", AC.solve(target));
    }
    return 0;
}