洛谷P3808 & P3796 AC自动机模板

题目：P3808：https://www.luogu.org/problemnew/show/P3808

P3796：https://www.luogu.org/problemnew/show/P3796

从这里学了下AC自动机：http://www.cnblogs.com/cjyyb/p/7196308.html

我的理解大概就是构建一棵由模式串组成的 Trie 树，然后把文本串一节一节放在上面查找；

失配指针指向的是结尾字母和自己一样的、Trie 树上的其他分支，大约就是在找后缀这样的感觉；

所以文本串每加入一个字符，就在 Trie 树上查找以这个字符结尾的后缀模式串，所以能找到所有出现过的；

慕名已久的AC自动机原来也挺简单的嘛！

代码如下：

P3808：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int const maxn=1e6+;

int n,cnt;

queue<int>q;

struct N{

    int fail,son[],end;

}AC[maxn];

void build(string s)

{

    int l=s.length();

    int nw=;

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

    {

        if(AC[nw].son[s[i]-'a']==)AC[nw].son[s[i]-'a']=++cnt;

        nw=AC[nw].son[s[i]-'a'];

    }

    AC[nw].end++;

}

void get_fail()

{

    AC[].fail=;

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

    {

        if(AC[].son[i]==)continue;

        AC[AC[].son[i]].fail=;

        q.push(AC[].son[i]);

    }

    while(q.size())

    {

        int x=q.front(); q.pop();

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

        {

            if(AC[x].son[i])

            {

                AC[AC[x].son[i]].fail=AC[AC[x].fail].son[i];

                q.push(AC[x].son[i]);

            }

            else AC[x].son[i]=AC[AC[x].fail].son[i];

        }

    }

}

int query(string s)

{

    int l=s.length();

    int ret=,nw=;

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

    {

        nw=AC[nw].son[s[i]-'a'];

        for(int t=nw;t&&AC[t].end!=-;t=AC[t].fail)

        {

            ret+=AC[t].end;

            AC[t].end=-;

        }

    }

    return ret;

}

int main()

{

    scanf("%d",&n);

    string s;

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

    {

        cin>>s;

        build(s);

    }

    get_fail();

    cin>>s;

    printf("%d\n",query(s));

    return ;

}

P3796：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const maxn=1e6+;

int n,cnt;

queue<int>q;

string s[];

struct N{

    int son[],fail,end;

}AC[maxn];

struct P{int num,pos;}ans[];

bool cmp(P x,P y)

{

    if(x.num==y.num)return x.pos<y.pos;

    else return x.num>y.num;

}

void clear(int x)

{

    memset(AC[x].son,,sizeof AC[x].son);

    AC[x].fail=; AC[x].end=;

}

void build(string s,int num)

{

    int l=s.length();

    int nw=;

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

    {

        if(!AC[nw].son[s[i]-'a'])AC[nw].son[s[i]-'a']=++cnt,clear(cnt);

        nw=AC[nw].son[s[i]-'a'];

    }

    AC[nw].end=num;

}

void get_fail()

{

    while(q.size())q.pop();

    AC[].fail=;

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

    {

        if(AC[].son[i]==)continue;

        AC[AC[].son[i]].fail=; q.push(AC[].son[i]);

    }

    while(q.size())

    {

        int x=q.front(); q.pop();

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

        {

            if(AC[x].son[i])

            {

                AC[AC[x].son[i]].fail=AC[AC[x].fail].son[i];

                q.push(AC[x].son[i]);

            }

            else AC[x].son[i]=AC[AC[x].fail].son[i];

        }

    }

}

void query(string s)

{

    int l=s.length();

    int nw=;

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

    {

        nw=AC[nw].son[s[i]-'a'];

        for(int t=nw;t/*&&t.end!=-1*/;t=AC[t].fail)

        {

            ans[AC[t].end].num++;

//            AC[t].end=-1;

        }

    }

}

int main()

{

    while()

    {

        scanf("%d",&n);

        if(!n)return ;

        cnt=; clear();

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

        {

            cin>>s[i];

            build(s[i],i);

            ans[i].pos=i;

            ans[i].num=;//

        }

        get_fail();

        cin>>s[];

        query(s[]);

        sort(ans+,ans+n+,cmp);

        printf("%d\n",ans[].num);

        cout<<s[ans[].pos]<<endl;

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

        {

            if(ans[i].num==ans[i-].num)

                cout<<s[ans[i].pos]<<endl;

            else break;

        }

    }

}

巴特西

洛谷P3808 & P3796 AC自动机模板

最新文章

热门文章