HDU 2222(AC自动机)

Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters ‘a’-‘z’, and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.

Output
Print how many keywords are contained in the description.

Sample Input

1
5
she
he
say
shr
her
yasherhs

Sample Output

3

题目大意：给出n个单词，然后给出一段文本，问在文本中有多少个单词出现过。

解题思路：这是一道AC自动机的板子题，跑一遍AC自动机的板子就可以啦。

AC自动机主要是在trie树上加了一个fail指针匹配，如果一个单词的某一个后缀与另一个单词的前缀相等，那么该位置的fail指针指向相等的这一部分。
(因为AC自动机主要靠trie树的思想，其实指针失配很容易就看懂了，所以建议先理解trie树算法再来看AC自动机更好。emm ，如果可以，也可以再看一下KMP算法。)
比如该题中的样例：

上图就是我们得到的trie树，箭头表示fail指针指向（PS：因为没有不同颜色的笔，所以只画了这两个结点的fail指针的指向，其他的结点的fail指针都指向0）。我们可以看到she这个字符串和her这个字符串相比较，she的后缀等于he的前缀，因为有了这个fail指针，如果我们搜索到she，已经匹配到e这个字符的情况下，我们也相当于匹配到he这个字符串的所有字符，而在创建这个trie树时，he这条路径中e字符的结点已经有值了，即出现过，那么我们加上这个值就可以了，然后我们将her中的r加在she的后面，这样就可以继续匹配her这个字符串是否出现过啦。而我们得到fail树的方法一般是使用BFS，我们先将第一层的结点加入队列，然后再去寻找每一个结点的子节点，再加入队列，说起来，AC自动机的原理就是这样子啦。接下来看代码叭。
AC代码：

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <bitset>
#include <queue>
//#include <random>
#include <time.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ls root<<1
#define rs root<<1|1
const int inf=1ll*1<<60;
const int maxn=5e5+10;
const int maxm=1e6+10;
int to[maxn][27],cnt[maxn];
char arr[maxm];
int tot,fail[maxn];
void add(char *s)//创建trie树
{
    int now=0;
    for(int i=0;s[i]!='\0';i++){
        int x=s[i]-'a';
        if(!to[now][x]){
            to[now][x]=++tot;
        }
        now=to[now][x];
    }
    cnt[now]++;
}
void getfail()
{
    queue<int> q;
    for(int i=0;i<26;i++){
        if(to[0][i])q.push(to[0][i]);//先将第一层的结点加入队列
    }
    while(!q.empty()){
        int x=q.front();q.pop();//取出一个结点
        for(int i=0;i<26;i++){//遍历可能存在的结点
            if(to[x][i]){//如果存在，那么就将它的fail指针指向他父亲结点fail指针指向的结点相对应的子节点
                    //因为父亲结点已经匹配了，那么父亲结点的相对应的儿子结点就是该节点所匹配的结点。
                fail[to[x][i]]=to[fail[x]][i];
                q.push(to[x][i]);
            }
            else to[x][i]=to[fail[x]][i];//如果不存在，那么就将父亲结点fail指针指向的结点相对应的子结点放入该节点，以便匹配可能存在的另一个单词。
        }
    }
}
int query(char *s)
{
    int now=0,ans=0;
    for(int i=0;s[i]!='\0';i++){
        int x=s[i]-'a';
        now=to[now][x];
        for(int j=now;j && cnt[j]!=-1;j=fail[j]) ans+=cnt[j],cnt[j]=-1;//在trie树中，如果匹配到了一个结点，那么如果该节点指向的fail指针存在，那么这个单词就出现过，所以遍历所有的fail指针指向的结点
        //因为可能会计算重复，所以加完之后，就将该结点的出现次数变为-1，也可以减少循环次数。
    }
    return ans;
}
signed main()
{
    int T;
    cin>>T;
    while(T--){
        int n;
        scanf("%lld",&n);
        tot=0;
        memset(cnt,0,sizeof cnt);
        memset(fail,0,sizeof fail);
        memset(to,0,sizeof to);
        while(n--){
            scanf("%s",arr);
            add(arr);
        }
        getfail();
        scanf("%s",arr);
        printf("%lld\n",query(arr));
    }
}