[BZOJ3172][Tjoi2013]单词 Fail树


原题链接
介绍一下fail树:
我们知道,AC自动机中每个节点有且仅有一个fail指针,因此将所有非根节点的fail指针反向,就得到了一棵树,这棵树叫做fail树.fail树上每个节点代表某个前缀,且父亲是儿子的后缀.
对于这道题,考虑到子串=前缀的后缀,因此只需要计算有多少前缀的后缀是当前串即可,也就是当前串是多少前缀的后缀,也就是fail树上当前串的子树中每个前缀的出现次数之和.
因此建自动机的时候将经过的节点都加上1最后统计fail树上的子树size即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
int n;
char s1[N];
struct Node
{
    int ch[26],fail,cnt;
    Node(){memset(ch,-1,sizeof ch),fail=cnt=0;}
}a[N];
struct edge
{
    int to,nxt;
}e[N];
int head[N],cnt,size[N];
inline void add(int x,int y)
{
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}
int tot,root;
inline int newnode()
{
    a[++tot]=Node();
    return tot;
}
int id[233];
inline int insert(char *str)
{
    int len=strlen(str),x=root;
    for(int i=0;i<len;++i)
    {
        if(a[x].ch[str[i]-'a']<0)a[x].ch[str[i]-'a']=newnode();
        x=a[x].ch[str[i]-'a'];a[x].cnt++;
    }
    return x;
}
int q[N],l=1,r;
void build_fail()
{
    a[root].fail=root;
    int x,i;
    for(i=0;i<26;++i)
    {
        if(a[root].ch[i]<0)a[root].ch[i]=root;
        else a[a[root].ch[i]].fail=root,q[++r]=a[root].ch[i];
    }
    while(l<=r)
    {
        x=q[l++];
        add(a[x].fail,x);
        for(i=0;i<26;++i)
        {
            if(a[x].ch[i]<0)a[x].ch[i]=a[a[x].fail].ch[i];
            else a[a[x].ch[i]].fail=a[a[x].fail].ch[i],q[++r]=a[x].ch[i];
        }
    }
}
inline void getans(int x)
{
    size[x]=a[x].cnt;
    for(int i=head[x];i;i=e[i].nxt)
    {
        getans(e[i].to);
        size[x]+=size[e[i].to];
    }
}
int main()
{
    root=newnode();
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s1);
        id[i]=insert(s1);
    }
    build_fail();
    getans(root);
    for(int i=1;i<=n;++i)printf("%d\n",size[id[i]]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注