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

发表回复

Avatar placeholder

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