AC自动机

#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#include <cctype>
using namespace std;
inline void read(int &x)
{
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    x*=f;
}
inline void print(int x)
{
    if(x<0){x=-x;putchar('-');}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,sum;
char p[1000100];
int trie[500500][26];
int mk[500500];//标记次节点单词个数 
int faq[500500]; //失配指针 
queue<int>q;
int main()
{
   read(n);
   for(int i=1;i<=n;i++)
   {
           scanf("%s",p+1);
           int len=strlen(p+1),rt=0;
           for(int j=1;j<=len;j++)
           {
               int id=p[j]-'a';p[j]='\0';
               if(!trie[rt][id]) trie[rt][id]=++sum;
               rt=trie[rt][id];
        }
        mk[rt]++;
   }//建trie树 

   for(int i=0;i<=25;i++) if(trie[0][i]) faq[trie[0][i]]=0,q.push(trie[0][i]);
   //与根节点0相连的点的faq全指向0(作为模式串开头字母如果无法匹配只能到根节点上),并把存在的节点进队等待处理 
   while(!q.empty())
   {
        int u=q.front();q.pop();
        for(int i=0;i<=25;i++)
        {
            if(trie[u][i]) faq[trie[u][i]]=trie[faq[u]][i],q.push(trie[u][i]);
            //如果当前位置下有这个字母节点，则其失配指针指向当前位置的失配指针下的该节点；
            //若当前位置的失配指针下没有当前遍历的该字母节点，任不影响（为0，指向超级节点）； 
            else trie[u][i]=trie[faq[u]][i];
            //当前位置下没有这个节点；就调到它失配指针所指向的节点下的此个字母节点； 
            //若为0，不影响，指向根节点;
        }
   }
       //造机原理：
       //若当前节点为A，其父节点为B，B的fail为C，那么C所代表的字符串一定是B的最长的后缀。
    //如果C有一个儿子D的字符与A的字符等同，那么显然D所代表的串（C加一个字符）就是A所代表的串（B加一个字符）的最长后缀。
    //如果C没有一个儿子，使其字符与A的字符等同呢？很简单，只需要再访问C的fail就行了。
    //如此反复，直到A的最长后缀找到，或者A的fail指向根节点为止。 
    scanf("%s",p+1);
    int len=strlen(p+1),rt=0,ans=0;
    for(int i=1;i<=len;i++)
    {
        rt=trie[rt][p[i]-'a'];//当前位置的下一个节点位置；
        for(int j=rt;j&&mk[j];j=faq[j]) ans+=mk[j],mk[j]=0;
        //当此节点存在同时其单词个数未被统计；
        //将答案加上所搜索的字符串中所包含的该单词数 ； 
        //标记已经统计
        //直接将位置指向其失配指针的位置（节约时间）； 
    }
    printf("%d\n",ans);
    return 0;
}