首页 > 其他 > 详细

BZOJ.5137.Standing Out from the Herd(广义后缀自动机)

时间:2018-09-20 21:04:23      阅读:223      评论:0      收藏:0      [点我收藏+]

题目链接

\(Description\)

对于每个串,求在\(n\)个串中只在该串中出现过的子串的数量。

\(Solution\)

建广义SAM。对每个串插入时新建的np标记其属于哪个串。
然后在parent树上DFS,合并子节点状态就行了。
每个点的贡献就是\(len[i]-len[fa[i]]\)

因为这样的广义SAM不是很正规吧,直接按拓扑序倒序递推是错的。(见评论 https://www.cnblogs.com/cjyyb/p/9100377.html

//26700kb   244ms
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=2e5+5;

struct Suffix_Automaton
{
    int tot,las,son[N][26],len[N],fa[N],bel[N],Enum,H[N],nxt[N],to[N];
    char s[N>>1];
    long long ans[N>>1];

    #define AE(u,v) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum
    Suffix_Automaton() {tot=las=1;}
    void Insert(int c,int id)
    {
        int np=++tot,p=las;
        len[las=np]=len[p]+1, bel[np]=id;
        for(; p&&!son[p][c]; p=fa[p]) son[p][c]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][c];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot; len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof son[q]);
                fa[nq]=fa[q], fa[q]=fa[np]=nq;
                for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;
            }
        }
    }
    void Build(int id)
    {
        las=1;  scanf("%s",s);
        for(int i=0,l=strlen(s); i<l; ++i) Insert(s[i]-'a',id);
    }
    void DFS(int x)
    {
        for(int i=H[x]; i; i=nxt[i]) DFS(to[i]);
        for(int i=H[x],v; i; i=nxt[i])
        {
            if(!bel[v=to[i]]) {bel[x]=0; break;}
            if(!bel[x]) bel[x]=bel[v];
            else if(bel[x]!=bel[v]) {bel[x]=0; break;}
        }
    }
    void Solve(int n)
    {
        for(int i=2; i<=tot; ++i) AE(fa[i],i);
        DFS(1);
        for(int i=2; i<=tot; ++i) if(bel[i]) ans[bel[i]]+=len[i]-len[fa[i]];
        for(int i=1; i<=n; ++i) printf("%lld\n",ans[i]);
    }
}sam;

int main()
{
    int n; scanf("%d",&n);
    for(int i=1; i<=n; ++i) sam.Build(i);
    sam.Solve(n);
    return 0;
}

BZOJ.5137.Standing Out from the Herd(广义后缀自动机)

原文:https://www.cnblogs.com/SovietPower/p/9683080.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!