[HDU 2896]病毒侵袭[AC自动机]

题意:

多模式串匹配,输出模式串的ID

思路:

典型AC自动机.

用向量存储答案ID

#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <string>#include <algorithm>using namespace std;const int MAXL = 130;/*inline int GetID(char x){    return x;}*/class node{public:    node* chd[MAXL];    node* fail;    int cnt;    node(){        fail = NULL;        memset(chd,0,sizeof(chd));        cnt = 0;    }};vector <int> ans;class AC_Automation{public:    node* root;    queue<node*> q;    AC_Automation(){        root = new node;        while(!q.empty())   q.pop();    }    void insert(string s,int x)    {        node* cur = root;        for(int i=0;i<s.length();i++)        {            int index = s[i];            if(cur->chd[index] == NULL)    cur->chd[index] = new node;            cur = cur->chd[index];        }        cur->cnt = x;    }    void BuildAC()    {        node *cur,*tmp;        q.push(root);        while(!q.empty())        {            cur = q.front();            q.pop();            for(int i = 0; i < MAXL ; i++ )            {                if(cur->chd[i])                {//只有root->fail = NULL;                    if(cur==root)   cur->chd[i]->fail = root;                    else                    {                        tmp = cur->fail;                        while(tmp->fail && !tmp->chd[i])    tmp = tmp->fail;                        if(tmp->chd[i])     cur->chd[i]->fail = tmp->chd[i];                        else    cur->chd[i]->fail = root;                    }                    q.push(cur->chd[i]);                }            }        }    }    void query(string s)    {//用指针时,指向根节点和指向空要分别对待;在fail的构造中已经解决了指向根的跳回        //只需要注意指向空的时候跳回指向根        node *cur = root, *tmp;        for(int i=0;i<s.length();i++)        {            int index = s[i];            if(cur->chd[index]) cur = cur->chd[index];            else            {                while(cur && !cur->chd[index])  cur = cur->fail;                if(!cur)    cur = root;                if(cur->chd[index])     cur = cur->chd[index];            }            tmp = cur;            while(tmp->chd && tmp->cnt)            {                ans.push_back(tmp->cnt);                if(ans.size()==3)   return;                tmp = tmp->fail;            }        }    }};char pat[205],tar[10005];int main(){    int n;    while(scanf("%d",&n)==1)    {        AC_Automation AC;        for(int i=1; i<=n; i++)        {            getchar();            gets(pat);            AC.insert(pat,i);        }        AC.BuildAC();        int m,tot = 0;        scanf("%d",&m);        for(int i=1;i<=m;i++)        {            getchar();            gets(tar);            ans.clear();            AC.query(tar);            if(ans.size())            {                sort(ans.begin(),ans.end());                printf("web %d:",i);                for(int j=0;j<ans.size();j++)   printf(" %d",ans[j]);                puts("");                tot++;            }        }        printf("total: %d\n",tot);    }}