[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)

发布于 2018-03-20  65 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)

Description

某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。

Tag

AC自动机

解决思路

考虑在AC自动机中如何处理一个问题,一个字符串x出现在另一个字符串y中的某一位置,当且仅当这个位置的结尾可以通过跳Fail跳到x的结尾。
把问题放到Fail树上考虑,就变成了统计Fail树上每一个点的子树大小,一遍dfs扫描。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=2000010;
const int maxM=maxN*2;
const int maxAlpha=27;
const int inf=2147483647;

class Trie
{
public:
    int fail,cnt;
    int son[maxAlpha];
};

int n,nodecnt;
char str[maxN],input[maxN];
Trie T[maxN];
int Id[maxN];
int Queue[maxN];

namespace TC
{
    int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
    int Size[maxN];
    void init()
    {
        mem(Head,-1);return;
    }

    void Add_Edge(int u,int v)
    {
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
        return;
    }
    void dfs(int u,int fa)
    {
        Size[u]=T[u].cnt;
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            dfs(V[i],u);
            Size[u]+=Size[V[i]];
        }
        return;
    }
}

void Insert(char *str,int id);
void GetFail();
void dfs(int u);

int main()
{
    ios::sync_with_stdio(false);TC::init();
    cin>>n;
    int len=0;
    for (int i=1;i<=n;i++)
    {
        cin>>(input+1);
        int l=strlen(input+1);
        Insert(input,i);
        str[++len]='z'+1;
        for (int j=1;j<=l;j++) str[len+j]=input[j];
        len=len+l;
        Id[len]=i;
    }
    str[++len]='\0';
    //构建Fail
    GetFail();
    TC::dfs(0,0);//得到Fail树中每一个点的子树大小
    for (int i=1;i<=n;i++) cout<<TC::Size[Id[i]]<<endl;
    return 0;
}

void Insert(char *str,int id)
{
    int len=strlen(str+1);
    int now=0;
    for (int i=1;i<=len;i++)
    {
        if (T[now].son[str[i]-'a']==0) T[now].son[str[i]-'a']=++nodecnt;
        now=T[now].son[str[i]-'a'];
        T[now].cnt++;
    }
    Id[id]=now;
    return;
}

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<maxAlpha;i++) if (T[0].son[i]!=0) Queue[++h]=T[0].son[i];
    do
    {
        int u=Queue[++t];
        for (int i=0;i<maxAlpha;i++)
        {
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                Queue[++h]=T[u].son[i];
            }
            else T[u].son[i]=T[T[u].fail].son[i];
        }
    }
    while (t!=h);
    //建立Fail树
    for (int i=1;i<=nodecnt;i++) TC::Add_Edge(T[i].fail,i);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)


HNCJ OIer