HDU 2896(ACオートマチックテンプレート問題)

タイトルリンク:  http://acm.hdu.edu.cn/showproblem.php?pid=2896

複数のパターン列.複数の一致する列.ここで、列の文字範囲は(0~127)である.マッチング列にどのパターン列が含まれているかを尋ねます.
問題解決の考え方:
AC自動機テンプレート問題.文字範囲に注意してください.
cntはこのモード列の個数を記録してこのモード列のindexに変更する.
findの場合、見つけたindexをvectorに押し込めばいいです.
複数のマッチング列があることに注意してください.findのたびにlast->cntを変更します.1つのモード列がvectorに何度も押し込まれるのを防止するため、バックアップしてから復元します.
 

#include "cstdio"

#include "cstring"

#include "string"

#include "iostream"

#include "queue"

#include "vector"

#include "algorithm"

using namespace std;

#define maxn 130

struct Trie

{

    Trie *next[maxn],*fail;

    int cnt;

}*root;

struct status

{

    Trie *last;

    int cnt;

    status(Trie *last,int cnt):last(last),cnt(cnt) {}

};

Trie *newnode()

{

    Trie *ret=new Trie;

    memset(ret->next,0,sizeof(ret->next));

    ret->fail=0;

    ret->cnt=0;

    return ret;

}

void init() {root=newnode();}

void Insert(string str,int index)

{

    Trie *pos=root;

    for(int i=0;i<str.size();i++)

    {

        int c=str[i];

        if(!pos->next[c]) pos->next[c]=newnode();

        pos=pos->next[c];

    }

    pos->cnt=index;

}

void getfail()

{

    queue<Trie *> Q;

    for(int c=0;c<maxn;c++)

    {

        if(root->next[c])

        {

            root->next[c]->fail=root;

            Q.push(root->next[c]);

        }

        else root->next[c]=root;

    }

    while(!Q.empty())

    {

        Trie *x=Q.front();Q.pop();

        for(int c=0;c<maxn;c++)

        {

            if(x->next[c])

            {

                x->next[c]->fail=x->fail->next[c];

                Q.push(x->next[c]);

            }

            else x->next[c]=x->fail->next[c];

        }

    }

}

vector<int> find(string str)

{

    Trie *pos=root,*last;

    queue<status> Q;

    vector<int> ans;

    for(int i=0;i<str.size();i++)

    {

        int c=str[i];last;

        if(pos->next[c])

        {

            pos=pos->next[c];

            last=pos;

            while(last->cnt)

            {

                Q.push(status(last,last->cnt));

                ans.push_back(last->cnt);

                last->cnt=0; //  last->cnt

                last=last->fail;

            }

        }

    }

    while(!Q.empty()) //  last->cnt

    {

        status x=Q.front();Q.pop();

        x.last->cnt=x.cnt;

    }

    return ans;

}

int main()

{

    //freopen("in.txt","r",stdin);

    ios::sync_with_stdio(false);

    int n,m;

    string tt;

    while(cin>>n)

    {

        init();

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

        {

            cin>>tt;

            Insert(tt,i);

        }

        getfail();

        cin>>m;

        int cnt=0;

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

        {

            cin>>tt;

            vector<int> ans=find(tt);

            sort(ans.begin(),ans.end());

            if(!ans.size()) continue;

            cnt++;

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

            for(int j=0;j<ans.size();j++) printf(" %d",ans[j]);

            printf("
");

        }

        printf("total: %d
",cnt);

    }

}

 
 
2871595
neopenx
HDU
2896
Accepted
29988
343
C++
2565
9 min ago