HDU3065【AC自动机-AC感言】

Fourth AC zi dong ji(Aho-Corasick Automation) of life

9A（其实不止交了10发...）感言：

一开始多组数据这种小数据还是...无伤大局，因为改完以后还是wa...

一：

最后发现是wa在构造fail指针的时候在建立临时指针查询有没有匹配到的fail，在没有匹配到的时候，结点的fail的指针要指向根。

二（重要感言）：

在查询时，往上回溯fail指针的时候，fail指针是一定会最终回溯到根的，而且，比如当前查询到的主串是ABCDEF，fail指针可能会一直传递最终到根，但是并不是都有效啊！这里还要注意,fail指针传递过去，找到的是子串，还是本来那个串的后缀串，为什么说是子串：如果有模式串ABCD,ABCDEF，主串是ACBDEF，主串到D的时候已经处理掉了ABCD，这个情况下是不会用到fail指针的功效了，或者这里没有有效的后缀串；什么时候会用fail指针呢，如果有模式串CD，BCD,ABCDEF，主串是ACBDEF，那么在主串到D的时候会通过fail指针找到BCD，然后在找到CD，所以我们能得出，fail指针的回溯，当前串（比如ABCD）最后那个D是一直不会变的，可以说fail指针都是D的fail指针！

三：

不要依赖模板...

推荐几个数据：

2

CC

AAA

ooxxCC%dAAAoen....ENDooxxCC%dAAAoen....ENDooxxCC%dAAAoen....END

2

ABCDE

BCD

ABCD

2

ABCDE

BCD

ABCDEF

//#include <bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

/*

题意：

求不同的病毒出现的次数，未出现的不需要输出

AAA其中AA出现2次；

思路：

那我存的应该是编号了，编号都不同。

*/

const int N=5e4+10;

struct Trie

{

    int id;

    Trie *next[26],*fail;

};

Trie q[N],*root;

int tol,ans[1010],n;

char ss[1010][51];

Trie* Creat()

{

    Trie *p;

    p=&q[tol++];

    p->fail=NULL;

    p->id=0;

    for(int i=0; i<26; i++)

        p->next[i]=NULL;

    return p;

}

void Insert(char *str,int id)

{

    Trie *p=root;

    int index,len=strlen(str);

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

    {

        index=str[i]-'A';

        if(p->next[index]==NULL)

            p->next[index]=Creat();

        p=p->next[index];

    }

    p->id=id;

}

void Build_Ac()

{

    queue<Trie*>que;

    que.push(root);

    while(!que.empty())

    {

        Trie *p=que.front();que.pop();

        for(int i=0; i<26; i++)

        {

            if(p->next[i]!=NULL)

            {

                if(p==root)

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

                else

                {

                    Trie *temp=p->fail;

                    while(temp!=NULL)//找匹配的

                    {

                        if(temp->next[i]!=NULL) //找到

                        {

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

                            break;

                        }

                        temp=temp->fail;

                    }

                    if(temp==NULL)  //如果没有找到匹配的，则fail指向根

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

                }

                que.push(p->next[i]);

            }

        }

    }

}

char word[2000010];

void Query()

{

    int res=0;

    int index,len=strlen(word);

    Trie *p=root;

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

    {

        if(!(word[i]>='A'&&word[i]<='Z')){

            p=root;

            continue;

        }

        index=word[i]-'A';

        while(p->next[index]==NULL && p!=root)

            p=p->fail;

        p=p->next[index];

        if(p==NULL)

            p=root;

        Trie *temp=p;

        while(temp!=root)   //回溯到根

        {

            ans[temp->id]++;    //这里这样写没事，因为我不会用到id为0的，任他+

            temp=temp->fail;

        }

    }

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

    {

        if(ans[i])

            printf("%s: %d\n",ss[i],ans[i]);

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        tol=0;

        root=Creat();

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

        {

            ans[i]=0;

            scanf("%s",ss[i]);

            Insert(ss[i],i);

        }

        getchar();

        Build_Ac();

        gets(word);

        Query();

    }

    return 0;

}

；

巴特西

HDU3065【AC自动机-AC感言】

最新文章

热门文章