后缀自动机总结


一个不错的教程
T1:
暴力构造后缀自动机,略.
T2:
求一个串本质不同的子串数量.
线性构造后缀自动机后,直接统计每个状态有多少子串,最后加起来即可.每个状态的子串数量就直接用maxlen[x]-maxlen[pre[x]]求.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2002333
using namespace std;
typedef long long ll;
int n;
char s[N];
int last=1,tot=1,ch[N][26],mx[N],pre[N];
inline void add(int x)
{
    int p=last,np=++tot;
    last=np,mx[np]=mx[p]+1;
    for(;p&&!ch[p][x];p=pre[p])ch[p][x]=np;
    if(!p)pre[np]=1;//最简单的情况,如abcd->abcde,e这个字符第一次出现
    else
    {
        int q=ch[p][x];
        if(mx[q]==mx[p]+1)pre[np]=q;//较为简单的情况,如abcab->abcabc,ab到abc是一个关键转移,没有其他状态产生
        else
        {
            int nq=++tot;//最复杂的情况,如abcdbc->abcdbcd,bc到abcd是一个非关键转移,现在bcd和abcd不是一个状态了,需要为bcd新开一个状态(bcd左边出现了一个新字符)
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq;
            for(;p&&ch[p][x]==q;p=pre[p])ch[p][x]=nq;
        }
    }
}
ll ans;
int T;
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int i;
    for(i=1;i<=n;++i)add(s[i]-'a');
    for(i=1;i<=tot;++i)ans+=mx[i]-mx[pre[i]];
    printf("%lld\n",ans);
    return 0;
}

T3:
求单个串长度为k的子串中,最多的重复次数.
只需要统计每个状态的大小,就可以对其子串长度范围内进行更新了.容易得到

其实就相当于求st的pre树子树中有多少个前缀节点,然后就能更新了.
那么怎么快速更新呢?注意到答案关于i肯定是单调不增的,所以只需要对每个状态更新ans[maxlen[st]],最后从右往左扫一遍即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2002333
using namespace std;
int n;
char s[N];
int ch[N][26],sonnum[N],pre[N],mx[N],size[N],last=1,tot=1;
bool isnp[N];
inline void add(int x)
{
    int p=last,np=++tot;
    last=np,mx[np]=mx[p]+1;
    isnp[np]=1;
    for(;p&&!ch[p][x];p=pre[p])ch[p][x]=np;
    if(!p)pre[np]=1;
    else
    {
        int q=ch[p][x];
        if(mx[p]+1==mx[q])pre[np]=q;
        else
        {
            int nq=++tot;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq;
            sonnum[nq]=1;
            for(;p&&ch[p][x]==q;p=pre[p])ch[p][x]=nq;
        }
    }
    sonnum[pre[np]]++;
}
int q[N],maxx[N],l=1,r;
void topsort()
{
    int x;
    for(x=1;x<=tot;++x)if(!sonnum[x])q[++r]=x;
    while(l<=r)
    {
        x=q[l++],size[x]+=isnp[x];
        maxx[mx[x]]=max(maxx[mx[x]],size[x]);
        if(pre[x])
        {
            sonnum[pre[x]]--,size[pre[x]]+=size[x];
            if(!sonnum[pre[x]])q[++r]=pre[x];
        }
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int i;
    for(i=1;i<=n;++i)add(s[i]-'a');
    topsort();
    for(i=n;i;--i)maxx[i]=max(maxx[i],maxx[i+1]);
    for(i=1;i<=n;++i)printf("%d\n",maxx[i]);
    return 0;
}

T4:
求n个数字串的所有本质不同子串代表的数字的和,允许有前导0.
将数字串中间加特殊符号拼成一个长串,就可以正常建后缀自动机了,然后想办法对每个状态所代表的所有子串求和.
发现这个东西可以从起始状态按照拓扑序递推:

其中subnum为一个状态的子串数量,其实就是后缀自动机上s节点到该节点的路径条数,顺便也递推一遍就行了.
还有就是不能通过特殊字符的边更新答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 4002333
using namespace std;
const int mod=1000000007;
typedef long long ll;
int num,s[N];
char str[N];
int ch[N][11],pre[N],mx[N],ind[N],last=1,tot=1;
ll ans[N],sub[N];
inline void add(int x)
{
    int p=last,np=++tot;
    last=np,mx[np]=mx[p]+1;
    for(;p&&!ch[p][x];p=pre[p])ch[p][x]=np,ind[np]++;
    if(!p)pre[np]=1;
    else
    {
        int q=ch[p][x];
        if(mx[p]+1==mx[q])pre[np]=q;
        else
        {
            int nq=++tot;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            for(int i=0;i<=10;++i)if(ch[nq][i])ind[ch[nq][i]]++;
            pre[nq]=pre[q],pre[q]=pre[np]=nq,mx[nq]=mx[p]+1;
            for(;p&&ch[p][x]==q;p=pre[p])ind[q]--,ind[nq]++,ch[p][x]=nq;
        }
    }
}
int q[N],l=1,r;
ll sum;
inline void topsort()
{
    q[++r]=1;
    sub[1]=1;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=0;i<=10;++i)if(y=ch[x][i])
        {
            ind[y]--;
            if(i!=10)sub[y]=(sub[y]+sub[x])%mod,ans[y]=(ans[y]+ans[x]*10+i*sub[x])%mod;
            if(!ind[y])q[++r]=y;
        }
    }
}
int main()
{
    cin>>num;
    int i,j,len;
    for(i=1;i<=num;++i)
    {
        scanf("%s",str+1);
        len=strlen(str+1);
        for(j=1;j<=len;++j)add(str[j]-'0');
        if(i!=num)add(10);
    }
    topsort();
    for(i=1;i<=tot;++i)sum=(sum+ans[i])%mod;
    cout<<sum;
    return 0;
}

T5:
求一些字符串在原串中的循环同构串的数量.
首先需要掌握后缀自动机应用于字符串匹配(最长公共子串)的操作:对母串建立后缀自动机,将子串放进去跑,中间维护当前节点x和匹配长度len,然后枚举子串的每个字符:
如果trans[x][c]存在,则len++,x=trans[x][c];
否则沿着pre树一直往上跳,直到trans[x][c]存在或x=1为止,过程中len=maxlen[x].
对于求循环同构串的情况,我们将原串t倍增为t'(如t=aabbabd,t'=aabbabdaabbab),那么找循环同构串其实就是找t'长度为n的子串出现次数数量.注意:1.每个节点贡献只能计算一次 2.必须找到pre树上最靠近根的满足要求的状态,才能更新答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 202333
using namespace std;
int n,len;
char s[N],str[N];
int pre[N],ch[N][26],mx[N],size[N],isnp[N],tot=1,last=1;
int sonnum[N];
inline void add(int x)
{
    int p=last,np=++tot;
    last=np,mx[np]=mx[p]+1,isnp[np]=1;
    for(;p&&!ch[p][x];p=pre[p])ch[p][x]=np;
    if(!p)pre[np]=1,sonnum[1]++;
    else
    {
        int q=ch[p][x];
        if(mx[q]==mx[p]+1)pre[np]=q,sonnum[q]++;
        else
        {
            int nq=++tot;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq,sonnum[nq]=2;
            for(;p&&ch[p][x]==q;p=pre[p])ch[p][x]=nq;
        }
    }
}
int q[N],l=1,r;
void topsort()
{
    int x;
    for(x=1;x<=tot;++x)if(!sonnum[x])q[++r]=x;
    while(l<=r)
    {
        x=q[l++];
        size[x]+=isnp[x];
        if(pre[x])
        {
            sonnum[pre[x]]--,size[pre[x]]+=size[x];
            if(!sonnum[pre[x]])q[++r]=pre[x];
        }
    }
}
int vis[N],tim;
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    int i,j,x,ans,now;
    for(i=1;i<=len;++i)add(s[i]-'a');
    topsort();
    cin>>n;
    for(i=1;i<=n;++i)
    {
        scanf("%s",str+1);
        len=strlen(str+1),ans=0,x=1,now=0,tim++;
        for(j=1;j<len;++j)str[len+j]=str[j];
        len=len*2-1;
        for(j=1;j<=len;++j)
        {
            while(!ch[x][str[j]-'a']&&pre[x])x=pre[x],now=mx[x];
            if(ch[x][str[j]-'a'])x=ch[x][str[j]-'a'],now++;
            while(mx[pre[x]]>=(len+1)/2)x=pre[x],now=mx[x];
            if(now>=(len+1)/2&&vis[x]!=tim)
            {
                vis[x]=tim;
                ans+=size[x];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

[BZOJ3238]
求lcp之和.
用后缀数组做过一遍,今天拿后缀自动机写了一发确实变快了呢
怎么做呢?假如我种了一棵后缀树,这题就好做了,直接统计后缀树每个节点的深度乘上以它为lca的点对数量,最后加一起.
那么该怎么种后缀树呢?对反串建立后缀自动机,然后pre树就是后缀树~想想pre树代表什么就知道原因啦~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
typedef long long ll;
ll c2(ll x){return x*(x-1)/2;}
ll ans,key[N];
char s[N];
int n,pre[N],mx[N],ch[N][26],size[N],sonnum[N],tot=1;
inline int extend(int p,int x)
{
    int np=++tot;
    mx[np]=mx[p]+1,size[np]=1;
    for(;p&&!ch[p][x];p=pre[p])ch[p][x]=np;
    if(!p)pre[np]=1,sonnum[1]++;
    else
    {
        int q=ch[p][x];
        if(mx[q]==mx[p]+1)pre[np]=q,sonnum[q]++;
        else
        {
            int nq=++tot;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq,sonnum[nq]=2;
            for(;p&&ch[p][x]==q;p=pre[p])ch[p][x]=nq;
        }
    }
    return np;
}
int q[N],l=1,r;
void topsort()
{
    int x;
    for(x=1;x<=tot;++x)if(!sonnum[x])q[++r]=x;
    while(l<=r)
    {
        x=q[l++];
        if(pre[x])
        {
            sonnum[pre[x]]--;
            size[pre[x]]+=size[x];
            if(!sonnum[pre[x]])q[++r]=pre[x];
        }
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int i,p=1;
    for(i=n;i>0;--i)p=extend(p,s[i]-'a');
    topsort();
    for(i=r;i;--i)
    {
        p=q[i];
        key[p]=c2(size[p]),key[pre[p]]-=key[p];
    }
    for(i=1;i<=tot;++i)ans+=key[i]*mx[i];
    printf("%lld\n",(ll)(n-1)*n*(n+1)/2-2*ans);
    return 0;
}

《后缀自动机总结》上有1条评论

发表评论

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