AC自动机模板题
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string.h> 5 #include <string> 6 #include <queue> 7 using namespace std; 8 const int N=1002; 9 char str[2000005],s1[N][52]; 10 int ch[50010][26]; 11 int val[50010],sz,n,root,fail[50010],count1[N]; 12 int newnode(){ 13 memset(ch[sz],-1,sizeof(ch[sz])); 14 val[sz]=-1; 15 return sz++; 16 } 17 void init(){ 18 sz=0; 19 root=newnode(); 20 } 21 void insert(char* st,int id){ 22 int len=strlen(st); 23 int now=root; 24 for(int i=0;i<len;i++){ 25 int &u=ch[now][st[i]-'A']; 26 if(u==-1)u=newnode(); 27 now=u; 28 } 29 val[now]=id; 30 count1[id]=0; 31 } 32 void getfail(){ 33 queue<int> q; 34 fail[root] = root; 35 for(int i=0;i<26;i++){ 36 int &u=ch[root][i]; 37 if(u!=-1){ 38 fail[u]= 0; 39 q.push(u); 40 } 41 else u=root; 42 } 43 while(!q.empty()){ 44 int now=q.front(); 45 q.pop(); 46 for(int i=0;i<26;i++){ 47 int u=ch[now][i]; 48 if(u==-1)ch[now][i]=ch[fail[now]][i]; 49 else { 50 fail[u]=ch[fail[now]][i]; 51 q.push(u); 52 } 53 } 54 } 55 } 56 void query(char *s){ 57 int len=strlen(s); 58 int now=root; 59 for(int i=0;i<len;i++){ 60 if(s[i]>'Z'||s[i]<'A')now=root; 61 else { 62 now=ch[now][s[i]-'A']; 63 int tem=now; 64 while(tem!=root){ 65 if(val[tem]!=-1)count1[val[tem]]++; 66 tem=fail[tem]; 67 } 68 } 69 } 70 } 71 int main(){ 72 int i; 73 while(scanf("%d",&n)!=EOF){ 74 init(); 75 for(i=1;i<=n;i++){ 76 scanf("%s",s1[i]); 77 insert(s1[i],i); 78 } 79 scanf("%s",str); 80 getfail(); 81 query(str); 82 for(i=1;i<=n;i++){ 83 if(count1[i]) 84 printf("%s: %d ",s1[i],count1[i]); 85 } 86 } 87 return 0; 88 }