最后一道模板题。
下面把AC自动机小结一下。请看新文章.....
这题如果只开26的next的数组的话。
在查询大串时，要注意的if( s[i] )当不符合条件时，不能浅显的continue,而要把p=root;
不然..... 那些在A-Z之外的字符会直接略去，相当于大串中没有A-Z之外的字符，结果可想而知！！
#include<iostream>
#include<string>
#include<cstdio>
#define MAX 26
using namespace std;char str[2222222];
char str0[1111][55];
int cnt[1111],queue[555555];
int root,tot;struct node
{int fail,id;int next[MAX];void init(){memset( next,0,sizeof(next) );fail=-1,id=0;}
}Tire[555555];void init()
{root=tot=0;Tire[root].init();memset( cnt,0,sizeof(cnt) );
}void insert( char *s,int id )
{int i=0,k;int p=root;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].id=id;
}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];}}}
}void query( char *s )
{int i=0,k;int p=root;while( s[i] ){k=s[i++]-'A';if( k<0||k>25 ){p=root;continue;}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 ){cnt[Tire[temp].id]++;temp=Tire[temp].fail;}}
}int main()
{int N;while( scanf( "%d\n",&N )!=EOF ){init();for( int i=1;i<=N;i++ ){scanf( "%s",&str0[i] );insert(str0[i],i);}build_ac_automation();scanf( "%s",&str );query(str);for( int i=1;i<=N;i++ ){if( cnt[i] )printf( "%s: %d\n",str0[i],cnt[i] );}}return 0;
}