题意：给定一些只含大写字母的病毒串，再给一个文本串，问文本串中每个病毒串各出现了多少次

题解：

就是用AC自动机，在每个节点末尾有个id记录是哪个单词的末尾，然后如果同时是多个单词的末尾就用一个next数组链状记录当前id的下一个值。

多组数据坑死人。坑死人。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7   8 const int N=50010,S=2000010,A=26;  9 int n,num,cnt[N],nt[N],fir[N],sum[N]; 10 char ss[N][65],s[S]; 11 queue
          
            q; 12 struct node{ 13 int id,fail,son[30]; 14 }a[N]; 15 16 void clear(int x) 17 { 18 a[x].id=a[x].fail=0; 19 memset(a[x].son,0,sizeof(a[x].son)); 20 } 21 22 void trie(char *c,int id) 23 { 24 int x=0,l=strlen(c); 25 for(int i=0;i
           
            ='A' && c[i]<='Z')) {x=0;continue;} 70 int ind=c[i]-'A'+1; 71 x=a[x].son[ind]; 72 int p=a[x].id; 73 while(p) 74 { 75 sum[p]++; 76 p=nt[p]; 77 } 78 } 79 } 80 81 int main() 82 { 83 freopen("a.in","r",stdin); 84 freopen("a.out","w",stdout); 85 while(scanf("%d",&n)!=EOF) 86 { 87 num=0; 88 clear(0); 89 memset(nt,0,sizeof(nt)); 90 memset(fir,0,sizeof(fir)); 91 memset(sum,0,sizeof(sum)); 92 scanf("%d",&n); 93 for(int i=1;i<=n;i++) 94 { 95 scanf("%s",ss[i]); 96 trie(ss[i],i); 97 } 98 buildAC(); 99 scanf("%s",s);100 find(s);101 for(int i=1;i<=n;i++) 102 if(sum[i]) printf("%s: %d\n",ss[i],sum[i]); 103 }104 105 return 0;106 }