What is 后缀自动机?

我们先来看一下字符串abbb的后缀自动机,接下来你可以通过这幅图来参考后缀自动机的概念。

灵魂画手litble

后缀自动机是一个可以处理一个字符串的有向无环图,它存在一个起始点,由很多个节点和很多条边组成,这些节点叫做状态,这些边叫做转移

后缀自动机每条边上都写有一个字母,那么我从起始点出发,任意走几步,一定会走出原串的一个子串。通过不同的走法,我可以获得原串的所有子串。而我到一个节点终止时获得的子串,是该节点可代表的子串。

一个节点可代表的子串,是原串某个前缀的若干长度连续的后缀。什么是“长度连续的后缀”呢?打个比方,对于字符串orzabsab,zab,rzab就是前缀orzab长度连续的后缀,当然,我举例的这几个子串不一定被同一个节点代表。

后缀自动机的一些相关定义

下面是几个定义。

step(x): 表示从起始点出发,最多走几步可以走到节点x,也就是节点x可以代表的最长子串的长度。有些资料里将其称为len

pre指针:与AC自动机的fail指针类似,是失配指针。pre(x) 可以代表的子串,x一定可以代表,并且pre(x)可以代表的子串,是x可以代表的子串的长度连续后缀,而且pre(x)可以代表的最长子串,是x可以代表的最短子串的长度减1。

假设有abcde这样一个字符串,这里的字母只是编号,不是字符串中的实际字符。如果x代表的字符串是bcde,cde的话,pre(x)代表的字符串就是de,或者de和e两者。

综合step的定义,聪明美丽善良可爱的你一定发现了,x可以代表的子串的长度,是原字符串某一前缀的,长度在区间 $[step(pre(x))+1,step(x)]$ 范围内的后缀,它可以代表的子串数量是$step(x)-step(pre(x))$个。

至于pre树呢?顾名思义,一种把所有pre指针提取出来的,和fail树类似的树。

right集合:又名end-pos集合(咋感觉后缀自动机的命名很不统一啊)。顾名思义,假设$t \in right(x)$。x节点可以代表的子串,是原串中以第t个字符结尾的前缀的后缀。

综合pre的定义,聪明美丽善良可爱的你一定发现了,任何节点的right集合一定是其pre的right集合的真子集。

如何构建后缀自动机

最开始,后缀自动机有一个起点,记为1号节点。

假设我已经插入了原串中的前t个字符,现在要插入第t+1个字符x。记last表示代表了前t个字符构成的字符串的那个节点。

首先,建立一个新节点np(记为实节点),令p=lastlast=np,则在p代表的每一个字符串后面,再加上字符x,都可以被np代表。

除此了p代表的这个字符串以外,这些字符串的后缀后面添加一个字符x,也能构成新的子串,所以我们不断将p顺着pre指针上跳,并给跳到的节点连一条x转移边。

int np=++SZ,p=last; last=np,step[np]=step[p]+1;
while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];

如果一路跳到了起点,则p的pre也只能是起点,因为没有任何其他的节点,可以代表前t+1个字符构成的前缀的后缀。

假设跳到的第一个有x转移边的p,从它出发走x转移边可以走到q。像AC自动机一样,q也有可能是np的pre,如果step[q]=step[p]+1,就直接令pre(np)=q即可。

但是如果step[q]>step[p]+1呢?假设我们跳到当前这个p之前处在的那个节点,记为k(则有pre(k)=p),显然np要能代表k的所有代表字符串加上字符x的字符串。k代表的字符串长度在区间$[step(p)+1,step(k)]$内,所以np就要能代表长度为step(p)+2的字符串。

但若step[q]>step[p]+1,则q不能是np的pre,因为step[q]+1>step[p]+2,于是我们就要把q拆开。

具体的方式是建立一个nq(记为虚节点),将q的所有pre啊,转移边啊什么的都给它来一份,并且所有沿着p继续往上,x转移边是q的也全部改成nq。令steq[nq]=step[p]+1,然后将q的pre设置为nq,p的pre也是nq了。

完整代码:

//初始last=SZ=1
void ins(int x) {
    int np=++SZ,p=last; last=np,step[np]=step[p]+1;
    while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++SZ;step[nq]=step[p]+1;
            for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q&&p) ch[p][x]=nq,p=pre[p];
        }
    }
}

聪明美丽善良可爱的你一定发现了,我并没有提到right集合。那么如何求出right集合呢?

很简单,所有的实节点,如果它是在添加第t个字符时被加的,那么它能代表的字符串包括前t个字符构成的前缀,也就是说,它是right集合里有t的step最大的节点。

所以假设实节点k的right集合里有t,从k开始沿着pre指针上跳,走到的那些节点的right集合里也有t。

广义后缀自动机

广义后缀自动机就是把所有串放到一个后缀自动机里一起处理。

每次往后缀自动机里添加一个字符串后,将last重新挪到1号节点上,再添加下一个字符串即可。

添加字符串$S_i$时,添加出来的所有实节点及它们在pre树上的祖先们代表的子串,都在字符串$S_i$中出现过。

于是我们可以利用一些类似于set启发式合并的方法,来得到每个节点在多少个字符串中出现过。

一些例题

例1

bzoj3998

对于t=0,就是将所有节点的sz都设为1。对于t=1,则sz为每个节点right集合的大小。然后拓扑图DP一遍,求出当你在某个节点上时,接着走或者直接停下,还能走出多少不同子串,记为sum。

假设你当前在节点now。

若sz(x)大于等于K,在此停下,否则K-=sz(x)。

从其a转移边到z转移边,枚举每条转移边到的节点x。若sum(x)大于等于K,则走向这个节点,否则K-=sum(x)。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=1000005;
char S[N];int ch[N][26],step[N],pre[N],T[N],a[N];
int sz[N],sum[N];
int ty,K,SZ,last,n;

void ins(int x) {
    int np=++SZ,p=last;
    last=np,step[np]=step[p]+1,sz[np]=1;
    while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++SZ;step[nq]=step[p]+1;
            for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q&&p) ch[p][x]=nq,p=pre[p];
        }
    }
}
void prework() {
    for(RI i=1;i<=SZ;++i) ++T[step[i]];//利用后缀自动机性质拓扑排序
    for(RI i=1;i<=SZ;++i) T[i]+=T[i-1];
    for(RI i=1;i<=SZ;++i) a[T[step[i]]--]=i;
    for(RI i=SZ;i>=1;--i)
        if(ty) sz[pre[a[i]]]+=sz[a[i]];
        else sz[i]=1;
    sz[1]=0;
    for(RI i=SZ;i>=1;--i) {
        int x=a[i];sum[x]=sz[x];//sum:停下或继续,你还能走出多少个子串
        for(RI j=0;j<26;++j) if(ch[x][j]) sum[x]+=sum[ch[x][j]];
    }
}
void work() {
    if(sum[1]<K) {puts("-1");return;}
    int now=1;
    while(1) {
        if(K<=sz[now]) break;
        K-=sz[now];
        for(RI i=0;i<26;++i)
            if(sum[ch[now][i]]<K) K-=sum[ch[now][i]];
            else {now=ch[now][i],printf("%c",i+'a');break;}
    }
}
int main()
{
    scanf("%s",S+1),n=strlen(S+1);
    scanf("%d%d",&ty,&K);
    last=SZ=1;for(RI i=1;i<=n;++i) ins(S[i]-'a');
    prework(),work();
    return 0;
}

例2

bzoj3238

首先把字符串反过来,前缀变后缀,然后建立后缀自动机(其实此时pre树就是原串的后缀树了诶)。那么假设代表前缀$t_1$的实节点$x$和代表前缀$t_2$的实节点$y$在pre树上的lca为节点$o$,那么step(o)就是$x$和$y$的最长公共后缀长度。

DP即可。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const int N=1000005;
char S[N];int ch[N][26],pre[N],step[N],T[N],p[N],sz[N];
int n,SZ,last,tot;LL ans;

void ins(int x) {
    int np=++SZ,p=last;
    last=np,step[np]=step[p]+1,sz[np]=1;
    while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++SZ;step[nq]=step[p]+1;
            for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q&&p) ch[p][x]=nq,p=pre[p];
        }
    }
}
void DP() {
    for(RI i=1;i<=SZ;++i) ++T[step[i]];
    for(RI i=1;i<=SZ;++i) T[i]+=T[i-1];
    for(RI i=1;i<=SZ;++i) p[T[step[i]]--]=i;
    for(RI i=SZ;i>=1;--i) {
        int x=p[i];
        ans+=1LL*sz[pre[x]]*sz[x]*step[pre[x]],sz[pre[x]]+=sz[x];
    } 
}
int main()
{
    scanf("%s",S+1),n=strlen(S+1);
    last=SZ=1;for(RI i=n;i>=1;--i) ins(S[i]-'a');
    DP();ans=1LL*(n-1)*n*(n+1)/2-ans*2;
    printf("%lld\n",ans);
    return 0;
}

例3

bzoj3277

终于到了激动人心的广义后缀自动机了。

set启发式合并处理每个节点代表了哪些字符串的子串,set集合的大小大于K的那些节点代表的子串就是符合条件的,就把这些节点的权值设为它代表的字符串个数(step(x)-step(pre(x))),否则设为0。

字符串$S_i$的所有实节点的祖先们的权值和,可以加到$S_i$的答案中。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const int N=200005;
char S[N];
int ch[N][26],pre[N],step[N],id[N];
int h[N],ne[N],to[N];LL val[N],ans[N];
set<int> orz[N];
int n,K,SZ,last,tot;

void ins(int ww,int x) {
    int np=++SZ,p=last;
    last=np,step[np]=step[p]+1,id[np]=ww,orz[np].insert(ww);
    while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++SZ;step[nq]=step[p]+1;
            for(RI i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q&&p) ch[p][x]=nq,p=pre[p];
        }
    }
}

typedef set<int>::iterator itr;
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs1(int x) {
    for(RI i=h[x];i;i=ne[i]) {
        dfs1(to[i]);
        if((int)orz[to[i]].size()>(int)orz[x].size()) swap(orz[to[i]],orz[x]);
        for(itr j=orz[to[i]].begin();j!=orz[to[i]].end();++j) orz[x].insert(*j);
        orz[to[i]].clear();
    }
    if((int)orz[x].size()>=K) val[x]=step[x]-step[pre[x]];
}
void dfs2(int x,LL nowval) {
    nowval+=val[x];
    if(id[x]) ans[id[x]]+=nowval;
    for(RI i=h[x];i;i=ne[i]) dfs2(to[i],nowval);
}
int main()
{
    scanf("%d%d",&n,&K);
    SZ=1;
    for(RI i=1;i<=n;++i) {
        scanf("%s",S+1);
        int len=strlen(S+1);last=1;
        for(RI j=1;j<=len;++j) ins(i,S[j]-'a');
    }
    for(RI i=2;i<=SZ;++i) add(pre[i],i);
    dfs1(1),dfs2(1,0);
    for(RI i=1;i<=n;++i) printf("%lld ",ans[i]);
    return 0;
}

参考资料

后缀自动机学习笔记 -Menci
WC2012后缀自动机讲解课件 -陈立杰
后缀自动机详解 -DZYO
对后缀自动机的一点理解 -PIPIBoss

题外话:子序列自动机

后缀自动机的一条路径是原串的一个子串,那么序列自动机上的一条路径就是原串的一个子序列
序列自动机很好写,就是每次查看最后出现过的一些表示字母x的节点,如果它们没有当前插入的字符y的儿子,那么就将它们的y儿子赋为当前节点,显然这样可以表示出原串的所有子串。

void ins(int x) {
    ++SZ,pre[SZ]=last[x];
    for(RI i=0;i<26;++i) {
        int now=last[i];
        while(!ch[now][x]) ch[now][x]=SZ,now=pre[now];
    }
    last[x]=SZ;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

yyb · 2018年2月26日 7:41 下午

此评论已被litble手动折叠
折叠原因:含有虚假信息

    konnyakuxzy · 2018年2月26日 8:47 下午

    Orz您太强了
    233333
    手动折叠
    膜拜litble是传播虚假信息哈哈哈哈
    笑死了QvQ

    litble · 2018年2月26日 8:53 下午

    Orz您太强了

konnyakuxzy · 2018年1月9日 8:51 下午

Orz太强了,都学后缀自动机了
我三兄弟还一个都不会,,,
赶紧学习惹QAQ

发表评论

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

你是机器人吗? =。= *