What is 后缀自动机？
我们先来看一下字符串 abbb 的后缀自动机，接下来你可以通过这幅图来参考后缀自动机的概念。
后缀自动机是一个可以处理一个字符串的有向无环图，它存在一个起始点，由很多个节点和很多条边组成，这些节点叫做状态，这些边叫做转移。
后缀自动机每条边上都写有一个字母，那么我从起始点出发，任意走几步，一定会走出原串的一个子串。通过不同的走法，我可以获得原串的所有子串。而我到一个节点终止时获得的子串，是该节点可代表的子串。
一个节点可代表的子串，是原串某个前缀的若干长度连续的后缀。什么是 “长度连续的后缀” 呢？打个比方，对于字符串 orzabs，ab,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=last，last=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
对于 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
首先把字符串反过来，前缀变后缀，然后建立后缀自动机（其实此时 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
终于到了激动人心的广义后缀自动机了。
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;
}
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