AC自动机模板，注意！ch,Fail,lab数组的大小不是n而是节点个数，需要认真计算！

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 10 using namespace std;11 12 int cnt;13 int ch[1100000][26],Fail[1100000],lab[1100000];14 char str[1100000],S[1100000];15 16 void Add(const char * s)17 {18 int p=0,i;19 for(i=1;s[i];++i)20 {21 if(!ch[p][s[i]-97])ch[p][s[i]-97]=++cnt;22 p=ch[p][s[i]-97];23 }24 lab[p]++;25 return ;26 }27 28 void Build()29 {30 int i,t;31 queue
              
                Q;32 Q.push(0);33 while(!Q.empty())34 {35 t=Q.front();Q.pop();36 for(i=0;i<26;++i)37 {38 if(ch[t][i])39 {40 Q.push(ch[t][i]);41 Fail[ch[t][i]]=t?ch[Fail[t]][i]:0;42 }43 else ch[t][i]=ch[Fail[t]][i];44 }45 }46 return ;47 }48 49 int main()50 {51 int T,n,i;52 53 scanf("%d",&T);54 while(T--)55 {56 memset(Fail,0,sizeof(Fail));57 memset(ch,0,sizeof(ch));58 memset(lab,0,sizeof(lab));59 cnt=0;60 scanf("%d",&n);61 for(i=1;i<=n;++i)62 {63 scanf("%s",str+1);64 Add(str);65 }66 Build();67 scanf("%s",S+1);68 int p=0,Ans=0;69 for(i=1;S[i];++i)70 {71 p=ch[p][S[i]-97];72 if(lab[p])73 {74 int pp=p;75 while(pp)Ans+=lab[pp],lab[pp]=0,pp=Fail[pp];76 }77 }78 printf("%d\n",Ans);79 }80 81 return 0;82 }