AC自动机 HDU 2896

n个字串

m个母串

字串在母串中出现几次

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<queue>

#include<vector>

 using namespace std;

 #define MAXN 130

//AC自动机

 class node

 {

public:

     int index;

     node * fail;

     node * next[MAXN];

     node()

     {

         index=;

         fail=;

         memset(next,,sizeof(next));

     }

 };

 node *root;

 //插入操作 来看自动机的肯定看过tire   没看过就别看了

 void Insert(char *s,int id)

 {

     node *p=root;

     while(*s)

     {

         int ind=*s-' ';

         if(!p->next[ind])

            p->next[ind]=new node;

         p=p->next[ind];

         s++;

     }

     p->index=id;

 }

 queue<node*>q1;

 void Build()

 {

     q1.push(root);

     root->fail=NULL;//根节点

     while(!q1.empty())

     {

        node *p=NULL;

        node *now=q1.front();

        q1.pop();

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

        {

            if(now->next[i]) //存在

            {

                if(now==root) //第二层的话直接就到根

                    now->next[i]->fail=root;

                else

                {

                    p=now->fail;

                    while(p) //从父亲节点开始找 一直到存在这个孩子节点相同的字母 其实就是后缀相同了

                    {

                        if(p->next[i])

                        {

                            now->next[i]->fail=p->next[i];

                            break;

                        }

                        p=p->fail;

                    }

                    if(p==NULL)

                        now->next[i]->fail=root;

                }

                q1.push(now->next[i]);

            }

        }

     }

 }

 bool flag[];

 vector<int>z[];

 char s1[];

 void Ques(char *s1,int id)

 {

    node *p=root;

    memset(flag,,sizeof(flag));

    int ind,len=strlen(s1);

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

    {

        ind=s1[i]-' ';

        while(p->next[ind]==NULL&&p!=root)//存在的

            p=p->fail;

        p=p->next[ind];

        if(!p)

            p=root;

        node *now=p;

        while(now!=root&&!flag[now->index])//一个一个检验 这边是否有可以匹配的 子串 后缀相同

        {

            if(now->index)

            {

                z[id].push_back(now->index);

                flag[now->index]=;

            }

            now=now->fail;

        }

        if(z[id].size()>=)

            break;

    }

 }

 int main()

 {

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         getchar();

         char s[];

         root=new node;

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

         {

             scanf("%s",s);

             Insert(s,i);

         }

         Build();

         int m;

         scanf("%d",&m);

         int ans=;

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

         {

             z[i].clear();

             scanf("%s",s1);

             Ques(s1,i);

             if(z[i].size()>)

             {

                 sort(z[i].begin(),z[i].end());

                 ans++;

             }

         }

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

         {

             if(z[i].size())

             {

                 printf("web %d:",i);

                 for(int j=;j<z[i].size();j++)

                    printf(" %d",z[i][j]);

                 printf("\n");

             }

         }

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

     }

     return ;

 }