菜不成声的 ac自动机刷题记录

HDU2222 Keywords Search

模板题。数组开小了结果会T。。。

代码

 #include <bits/stdc++.h>

 #define nmax 10010

 using namespace std;

 char in[nmax],b[];

 int t[*nmax][];

 int f[*nmax],v[nmax*];

 int n,cnt=,ans=;

 void ins(){

     int idx=,l=strlen(in);

     for (int i=; i<l; i++) {

         int x=in[i]-'a';

         if(!t[idx][x]) t[idx][x]=++cnt;

         idx=t[idx][x];

     }

     v[idx]++;

 }

 void init(){

     for (int i=; i<=cnt; i++) {

             for (int j=; j<; j++) t[i][j]=;

             f[i]=v[i]=;

     }

     cnt=;

     ans=;

 }

 void bf(){

     queue <int> q;

     for (int i=; i<; i++) if(t[][i]) q.push(t[][i]);

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for (int i=; i<; i++) {

             if( t[u][i] ) {

                 f[t[u][i]]=t[f[u]][i];

                 q.push(t[u][i]);

             }else t[u][i]=t[f[u]][i];

         }

     }

 }

 void solve(){

     int p=,l=strlen(b);

     for (int i=; i<l; i++) {

         int x=b[i]-'a';

         p=t[p][x];

         for (int j=p; j&&~v[j]; j=f[j]) ans+=v[j],v[j]=-;

     }

 }

 int main(){

     int cas;

     cin>>cas;

     while(cas--){

         init();

         scanf("%d",&n);

         for (int i=; i<n; i++) { scanf("%s",in); ins(); }

         bf();

         scanf("%s",b);

         solve();

         printf("%d\n",ans);

     }

     return ;

 }

o(*￣▽￣*)ブ

巴特西

菜不成声的 ac自动机刷题记录

HDU2222 Keywords Search

HDU2896 病毒侵袭

最新文章

热门文章

巴特西

菜不成声 的 ac自动机 刷题记录

HDU2222 Keywords Search

HDU2896 病毒侵袭

最新文章

热门文章

菜不成声的 ac自动机刷题记录