上一篇的姊妹篇
没啥好说的 套模板
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 50010 12 #define M 2000010 13 #define LL long long 14 #define INF 0xfffffff 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 const int child_num = 128; 19 int o[1010]; 20 char s[M],vir[1010][55]; 21 bool f[M]; 22 class ACAutomo 23 { 24 private: 25 int ch[N][child_num]; 26 int val[N]; 27 int fail[N]; 28 int Q[N]; 29 int id[128]; 30 int sz; 31 public: 32 void init() 33 { 34 fail[0] = 0; 35 for(int i = 0; i < child_num ; i++) 36 id[i] = i; 37 } 38 void reset() 39 { 40 memset(ch[0],0,sizeof(ch[0])); 41 sz = 1; 42 } 43 void insert(char *a,int key) 44 { 45 int p = 0 ; 46 for( ; *a ; a++) 47 { 48 int d = id[*a]; 49 if(ch[p][d]==0) 50 { 51 memset(ch[sz],0,sizeof(ch[sz])); 52 val[p] = 0; 53 ch[p][d] = sz++; 54 } 55 p = ch[p][d]; 56 } 57 val[p]=key; 58 } 59 void construct() 60 { 61 int i,head=0,tail = 0; 62 for(i = 0 ;i < child_num ; i++) 63 { 64 if(ch[0][i]) 65 { 66 Q[tail++] = ch[0][i]; 67 fail[ch[0][i]] = 0; 68 } 69 } 70 while(head!=tail) 71 { 72 int u = Q[head++]; 73 for(i = 0; i < child_num ; i++) 74 { 75 if(ch[u][i]) 76 { 77 Q[tail++] = ch[u][i]; 78 fail[ch[u][i]] = ch[fail[u]][i]; 79 } 80 else 81 ch[u][i] = ch[fail[u]][i]; 82 } 83 } 84 } 85 void work(char *s) 86 { 87 int i,k = strlen(s); 88 int p = 0; 89 for(i = 0 ;i < k ; i++) 90 { 91 int d = id[s[i]]; 92 p = ch[p][d]; 93 int tmp = p; 94 while(tmp!=0&&val[tmp]!=0) 95 { 96 o[val[tmp]]++; 97 tmp = fail[tmp]; 98 } 99 } 100 } 101 }ac; 102 int main() 103 { 104 int n,i; 105 ac.init(); 106 while(scanf("%d%*c",&n)!=EOF) 107 { 108 memset(o,0,sizeof(o)); 109 ac.reset(); 110 for(i = 1; i <= n; i++) 111 { 112 gets(vir[i]); 113 ac.insert(vir[i],i); 114 } 115 ac.construct(); 116 gets(s); 117 ac.work(s); 118 for(i = 1 ; i <= n ;i++) 119 if(o[i]) 120 printf("%s: %d ",vir[i],o[i]); 121 } 122 return 0; 123 }