HDU 2846(AC 자동 동기+다 중 텍스트 일치)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2846
제목:여러 텍스트,여러 패턴 문자열 이 있 습 니 다.각 패턴 문자열 에 몇 개의 텍스트 가 있 습 니까?매 칭 반복 가능)
문제 풀이 방향:
전통 적 인 AC 자동 동 기 는 하나의 텍스트 에서 패턴 문자열 의 출현 횟수 를 계산 하 는 것 이다.
여 기 는 특수 합 니 다.모든 텍스트 는 따로 계산 해 야 하 며,일치 하 는 텍스트 마다 한 번 만 계산 할 수 있 습 니 다.
예 를 들 어 add,d 는 한 번 만 계산 할 수 있 습 니 다.두 번.
그래서 텍스트 Find 를 하나씩 반복 합 니 다.각 Find 에서 Hash 를 진행 하여 매 칭 문자열 마다 1 회 만 계산 할 수 있 도록 합 니 다.
일치 하 는 문자열 이 중복 되 기 때문에 Insert 전에 Hash 를 분산 시 켜 서 중 복 된 아래 표 시 를 가장 먼저 삽입 한 아래 표 시 를 가리 키 도록 해 야 합 니 다.
또한,이 문 제 는 부정 확 한 AC 자동 동기 템 플 릿 을 끊 습 니 다.(Find 에 While(last!=while(last->cnct)대신 root) ）
코드

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include "cstdio"

#include "cstring"

#include "string"

#include "iostream"

#include "queue"

#include "vector"

#include "algorithm"

#include "map"

using namespace std;

#define maxn 26

int ans[100005],mt[100005];

string P[10005];

struct Trie

{

    Trie *next[maxn],*fail;

    int cnt;

}*root;

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]-'a';

        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];

        }

    }

}

void Find(string str)

{

    map<int,int> Hash;

    Trie *pos=root,*last;

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

    {

        int c=str[i]-'a';last;

        if(c<0||c>maxn) {pos=root;continue;}

        if(pos->next[c])

        {

            pos=pos->next[c];

            last=pos;

            while(last!=root)

            {

                if(!Hash.count(last->cnt))

                {

                    ans[last->cnt]++;

                    Hash[last->cnt]++;

                }

                last=last->fail;

            }

        }

    }

}

int main()

{

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

    ios::sync_with_stdio(false);

    int n,m,s;

    string tmp;

    while(cin>>n)

    {

        map<string,int> ms;

        memset(ans,0,sizeof(ans));

        memset(mt,0,sizeof(mt));

        init();

        for(int i=1;i<=n;i++) cin>>P[i];

        cin>>s;

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

        {

            cin>>tmp;

            if(!ms.count(tmp))

            {

                Insert(tmp,i);

                ms[tmp]=i;

                mt[i]=i;

            }

            else mt[i]=ms[tmp];

        }

        getfail();

        for(int i=1;i<=n;i++) Find(P[i]);

        for(int i=1;i<=s;i++) cout<<ans[mt[i]]<<endl;

    }

}