整整一天半都在弄AC自动机，我的第一道AC自动机。
DEBUG N久竟然是题目意思读错了！
题目大意：
给定Ｎ个单词，和一个模式串，求在单词模式串中出现的次数。
解题思路，先构造字典树，再对字典树进行ＡＣ自动机。
我ＤＥＢＵＧ Ｎ久.... 原来AC自动机都是构造的对的！
题目要注意的地方。
1.单词可以重复出现。
2.只是问最多有多少个单词出现在模式串中，最多为单词数N个。
继续切AC自动机的题目。最后写一篇总结
#include<iostream>
#include<cstdio>
#include<string.h>
#define MAX 26
using namespace std;int root,tot;
struct node
{int fail;int cnt;int next[MAX];void init(){memset( next,0,sizeof(next) );fail=-1;cnt=0;}
}Tire[5555555];
int queue[5555555];void init(){root=tot=0;Tire[root].init();
}void insert( int root,char *s ){int p=root;int i=0,k;while( s[i] ){k=s[i++]-'a';if( !Tire[p].next[k] ){Tire[++tot].init();Tire[p].next[k]=tot;}p=Tire[p].next[k];}Tire[p].cnt++;
}void build_ac_automation()
{int head,tail;head=tail=0;queue[tail++]=root;while( head<tail ){int cur=queue[head++];for( int i=0;i<MAX;i++ ){if( Tire[cur].next[i] ){int son=Tire[cur].next[i];int p=Tire[cur].fail;if( cur==root )Tire[son].fail=root;elseTire[son].fail=Tire[p].next[i];queue[tail++]=son;}else{int p=Tire[cur].fail;if( cur==root )Tire[cur].next[i]=root;elseTire[cur].next[i]=Tire[p].next[i];}}}
}int query( char *s )
{int i=0,k,p=root;int ret=0;while( s[i] ){k=s[i++]-'a';while( !Tire[p].next[k]&&p!=root )p=Tire[p].fail;p=Tire[p].next[k];if(p==-1) p=0;int temp=p;while( temp!=root&&Tire[temp].cnt!=-1 ){ret+=Tire[temp].cnt;Tire[temp].cnt=-1;//sTire[temp].cnt=0;temp=Tire[temp].fail;}}return ret;
}char str[1111111];
int main(){int T;scanf( "%d",&T );while( T-- ){init();int N;scanf( "%d",&N );while( N-- ){scanf( "%s",&str );insert( root,str );}build_ac_automation();scanf( "%s",&str );printf( "%d\n",query(str) );//system("pause");}return 0;
}