病毒侵袭
题意：统计长串中出现了哪些短串
用vector存一下，再输出
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define CLR(m,a) memset(m,a,sizeof(m)) 4 5 const int maxnode=500*200+10; 6 const int sigma=128; 7 8 struct AC 9 { 10 int ch[maxnode][sigma],last[maxnode],f[maxnode],val[maxnode]; 11 int sz; 12 vector<int> ans; 13 14 void init() 15 { 16 CLR(ch[0],0); 17 val[0]=0; 18 sz=1; 19 } 20 int idx(char c){return c;} 21 22 void inser(char *s,int v) 23 { 24 int u=0,n=strlen(s); 25 for(int i=0;i<n;i++){ 26 int c=idx(s[i]); 27 if(!ch[u][c]){ 28 CLR(ch[sz],0); 29 val[sz]=0; 30 ch[u][c]=sz++; 31 } 32 u=ch[u][c]; 33 } 34 val[u]=v; 35 } 36 37 void getfail() 38 { 39 queue<int> q; 40 f[0]=0; 41 for(int c=0;c<sigma;c++){ 42 int u=ch[0][c]; 43 if(u){ 44 q.push(u); 45 f[u]=0; 46 last[u]=0; 47 } 48 } 49 while(!q.empty()){ 50 int r=q.front(); 51 q.pop(); 52 for(int c=0;c<sigma;c++){ 53 int u=ch[r][c]; 54 if(!u) continue; 55 q.push(u); 56 int v=f[r]; 57 while(v&&!ch[v][c]) v=f[v]; 58 f[u]=ch[v][c]; 59 last[u]=val[f[u]]?f[u]:last[f[u]]; 60 } 61 } 62 } 63 void print(int u) 64 { 65 if(u){ 66 ans.push_back(val[u]); 67 print(last[u]); 68 } 69 } 70 void fin(char *s) 71 { 72 ans.clear(); 73 int u=0,n=strlen(s); 74 for(int i=0;i<n;i++){ 75 int c=idx(s[i]); 76 while(u&&!ch[u][c]) u=f[u]; 77 u=ch[u][c]; 78 if(val[u]) print(u); 79 else if(last[u]) print(last[u]); 80 } 81 } 82 }; 83 AC ac; 84 char s[210],t[10010]; 85 int n,m; 86 87 int main() 88 { 89 while(scanf("%d",&n)!=EOF) 90 { 91 ac.init(); 92 int cnt=0; 93 for(int i=1;i<=n;i++) 94 { 95 scanf("%s",s); 96 ac.inser(s,i); 97 } 98 ac.getfail(); 99 scanf("%d",&m); 100 for(int i=0;i<m;i++){ 101 scanf("%s",t); 102 ac.fin(t); 103 for(int j=0;j<ac.ans.size();j++) 104 { 105 sort(ac.ans.begin(),ac.ans.end()); 106 if(j==0){ 107 printf("web %d: %d",i+1,ac.ans[j]); 108 } 109 else printf(" %d",ac.ans[j]); 110 if(j==ac.ans.size()-1) cnt++,puts(""); 111 } 112 } 113 printf("total: %d ",cnt); 114 } 115 }