“后缀数组好$NB$啊!”

“那我们来学学更$NB$的后缀自动机吧!”


前言

先考虑一个问题:如何用一棵树表示出某个串的所有子串?

一个串的子串由它每个后缀的所有前缀组成。那么把它的每个后缀插到一棵$trie$树里,就能用根节点到任意节点表示出一个子串了。

然而这样时间空间都是$O(n^2)$的。于是就有了后缀自动机。

后缀自动机($Suffix\ AutoMaton$)又称子串自动机,是一张$DAG$,可以用最少的点线性时间与空间表示出每个后缀(最小性)。

如果说后缀数组是用来练习单调栈、二分和$ST$表的话,后缀自动机大概就是用来练习树形$DP$、图的$DP$和线段树合并吧(光速逃


抄袭来源

https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie (讲的很用心,大部分是抄他的

https://wavwing.top/2019/03/03/SAM%20Note (通过一些$PY$交♂易得到了密码)

https://0x131cc05.github.io/2019/03/21/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA/

https://oi-wiki.org/string/sam/

https://wenku.baidu.com/view/fa02d3fff111f18582d05a81.html ($clj$的讲稿还是比较专业的,免费的$ppt$这里可以下载)

https://www.cnblogs.com/asuldb/tag/SAM/ (题单主要来源)


#define

基本

$A[i,j]$:串$A$从第$i$个到第$j$个字符的组成的串

$length(A)$:串$A$的长度

$k$:字符集大小

$n$:一般情况下指母串长度

状态与转移:

$SAM$中每个点都有一个状态,记点$i$的状态为$T(i)$,根节点的状态为$T(0)$。每条边都是一个转移,一个状态可以通过转移成为一个新的状态。

很抽象。。。简单理解的话就是状态$T(i)$相当于从根节点走到$i$得到的字符串,转移相当于给当前字符串添加一个字符。

SAM​

$cnt$:$SAM$节点总数

$last$:当前串最长前缀的节点

$son[x][y]$(个人习惯$define$成$son(x,y)$):$SAM$中节点$x$走字符$’y’$到达的节点(类比于$trie$的边)

$fa[x]$:节点$x$在$SAM$中的父亲

$len[x]$:节点$x$代表的$endpos$等价类中,最长串的长度

$siz[x]$:节点$x$代表的$endpos$集合大小

$L(x)$:节点$x$代表的$endpos$等价类中的最长串


endpos

定义

对于字符串$S$任意一个子串$A$,$A$可能在$S$中出现多次,它的$endpos$为其所有结束位置的集合,记为$endpos(A)$。

举个栗子:在串aaabaabab中,$endpos(“aab”)=\{4,7\}$,$endpos(“ab”)=\{4,7,9\}$

若$endpos(A)=endpos(B)$,称$A$与$B$属于同一个$endpos$等价类

对于一个串,就能把它划分成若干个$endpos$等价类。

并不想证明的引理

1.当且仅当串$B$以串$A$一个后缀的形式出现在$S$中时,则$endpos(A)=endpos(B)$

这个比较明显了吧。。。直观理解就好了。

2.对于串$A$与串$B$,假设$length(B)<length(A)$,要么$endpos(A)\subseteq endpos(B)$(当$B$是$A$的后缀时);要么$endpos(A)\cap endpos(B)=\varnothing$(当$B$不是$A$的后缀时)

当$B$不是$A$的后缀时,它们肯定不会有公共的结束位置。

当$B$是$A$的后缀时。显然若$length(A)>length(B)$,$siz[A]\le siz[B]$,再结合引理$1$,就有$endpos(A)\subseteq endpos(B)$

3.在同一个$endpos$等价类中,假设最长的串为$A$,则其余的串都是$A$的后缀,且它们长度是连续的。换句话说,设最长长度为$r$,最短为$l$,所有串的长度恰好覆盖了$[l,r]$

由引理$1$可得“其余的串都是$A$的后缀”。

若长度不是连续的,在$endpos$等价类$E$中,存在$A$的后缀$A’,A’’$满足$length(A’’)<length(A’)<length(A)$,$A,A’’\in E$,$A’\notin E$。则$siz[A’’]\ge siz[A’]\ge siz[A]$,且$siz[A’’]=siz[A]$,矛盾,所以引理成立。

(我在瞎扯)

其实上面的引理都很明显,证明了反而更晕。。。

4.$endpos$等价类的个数级别为$O(n)$(重点)

这是证明后缀自动机复杂度的重要引理。

对于一个$endpos$等价类$E$,在其中最长的串前添加一个字符,根据引理$2$,得到的串所属的$endpos$等价类一定是$E$的一个真子集,并且添加不同的字符得到的$endpos$等价类互不相交。所以在最长串前添加字符(保证新串还是母串子串),相当于将$E$分割成若干个不相交的子集,子集的个数不超过$E$的大小。

那么一切$endpos$等价类都是由$\{1,2,3…n\}$不断分割而来的,类比于线段树,总大小不超过$O(n)$


后缀链接

定义

对于一个$endpos$等价类$E$,记其中长度最大的串为$A_{max}$,最小的为$A_{min}$,由上面引理$3$可知其余所有串为$A_{max}$的后缀,且长度连续。取串$A’$为$A_{max}$最长且不属于$E$的后缀,把$A_{min}$链接上$A’$,就是后缀链接。

性质

1.$length(A_{min})=length(A’)+1$,$endpos(A_{min})\subseteq endpos(A’)$

2.所有的后缀链接构成一棵以$T(0)$为根的树

从任意一个$endpos$等价类出发,沿后缀链接走长度是严格递减的,最后一定走到$T(0)$

3.以$endpos$等价类建树,由一个类的子集向自己连边,得到的树和后缀链接树结构相同。每个节点是包含某一前缀若干长度单调递减的后缀,并由后缀链接成长度从1到前缀长度的后缀的并集。

我们称这棵树为$parent\ tree$。

比如说串$aababa$的$parent\ tree$长这样(图片来源,节点右边是这个类中最长的串):

根据引理$4$,$parent\ tree$的边数是$O(n)$级别的。

$SAM$跟这个有啥关系?

$SAM$的节点和$parent\ tree$的节点是相同的,只是边不一样。


SAM的构造

SAM​长啥样?

$SAM$的构造是在线的。通过逐个加入字符维护当前$SAM$。

先放一张$SAM$的图(以串$aaabaab$为例,图片绘自SAM Drawer):

好丑啊

黑边指向儿子,红边指向父亲,$Max$就是$len$,$size1$是$siz$

可以发现对于任意非根节点,从根节点到其所有黑色路径构成的串组成了其$endpos$等价类。红边构成了$parent\ tree$。

实现

#define son(x,y) son[x][y]
int len[maxn],fa[maxn],son[maxn][26],last=1,cnt=1,n;
char s[maxn];
void insert(int c){
    int p=last,ne=last=++cnt;
    len[ne]=len[p]+1;
    while(p&&!son(p,c))son(p,c)=ne,p=fa[p];
    if(!p)fa[ne]=1;//#case 1
    else {
        int q=son(p,c);
        if(len[q]==len[p]+1)fa[ne]=q;//#case 2
        else {
            int sp=++cnt;
            memcpy(son[sp],son[q],sizeof son[sp]);
            fa[sp]=fa[q],len[sp]=len[p]+1;
            fa[ne]=fa[q]=sp;
            while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];
        }//#case 3
    }
}
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(register int i=1;i<=n;++i)insert(s[i]-'a');
}

每次添加一个字符$c$后,受影响的是新最长前缀的所有后缀,也就是原串最长前缀的所有后缀$+\ ‘c’$。

一句句来看:

    int p=last,ne=last=++cnt;

$p$存了当前最长前缀所在的节点,$ne(new)$是新建节点,状态为当前最长前缀,更新一下$last$。

    len[ne]=len[p]+1;

$ne$存有当前串的前缀,$len$即为上一个串的前缀($last$)长度$+1$。

    while(p&&!son(p,c))son(p,c)=ne,p=fa[p];

从$p$开始往上跳,因为$p$是原串最长前缀,往上跳就是从长到短枚举它每一个后缀。!son(p,c)就说明还未出现过该状态$+\ ‘c’$这个子串,现在加上了就会出现在最后,向$ne$连边。

case 1

    if(!p)fa[ne]=1;

遍历完所有后缀都没有son(p,c)!=0的点,说明$’c’$就没有出现过,就把它向根节点连父亲。

case 2

    else {
        int q=son(p,c);
        if(len[q]==len[p]+1)fa[ne]=q;

现在跳到了第一个有$’c’$这条边的点。

用$q$记录$p$走$’c’$到的点。

len[q]==len[p]+1说明$q$代表的$endpos$等价类中只有$L(p)+’c’$,为$ne$的后缀,连$p$的父亲到$q$。同时这是第一个满足条件的点,再往上跳的点$len$只会更小,那就向最长的点连父亲。

case 3

现在$len[q]!=len[p]+1$了,也就是$len[q]>len[p]+1$。在点$q$的$endpos$等价类中,不止有$L(p)+’c’$,还有其他更长的串,并且这些更长的串都不是$ne$的后缀。如果是的话,由于它更长,在点$p$之前一定还有一个节点的$’c’$边指向它,也就跳不到$p$点。

这样$q$就被分成了$2$类:$length==len[p]+1$和$length>len[p]+1$

前者满足$ne$向它连父亲,但后者不满足,所以就要新建节点分开它们。

    int sp=++cnt;

新建节点$sp(split)$,包含$length==len[p]+1$的串。

    memcpy(son[sp],son[q],sizeof son[sp]);

复制儿子。

本来就都是同一类的,分裂只是因为有的串$endpos$多了一位,儿子没变。

    len[sp]=len[p]+1,fa[sp]=fa[q];

$sp$中只有$length==len[p]+1$的串,$len[sp]$自然是$len[p]+1$,父亲也是原父亲。

    fa[ne]=fa[q]=sp;

$ne$的父亲肯定指向只有$length==len[p]+1$的$sp$点,而$sp$的$endpos$比$q$多了一位(也就是新加进来的位置),$q$的父亲连向它。

    while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];

再往上跳更新儿子。因为$p$往上跳$L(p)+’c’$一定有最后一位,而$q$的$endpos$,真正有的是$sp$,所有连向$q$的点都要移情别恋到$sp$上。如果跳到儿子不是$q$的$p$,那么$son(p,c)$就是$q$的祖先。$q$的父亲是$sp$,$son(p,c)$就是$sp$的祖先了,满足$endpos$的关系,不需要修改了。

复杂度

空间

显然一个字符最多新建两个节点,每个节点存有$k$个儿子,复杂度为$O(nk)$。

当然可以以时间换空间,数组改为$map$,空间就是$O(n)$的。

时间

复杂度是$O(n)$的,如果开$map$的话是$O(n\log k)$的。当$k$较小时可以视为常数,还是$O(n)$的。

复杂度肯定只关心两个$while$和$memcpy$。

    while(p&&!son(p,c))son(p,c)=ne,p=fa[p];

这个$while$就是加边的,它的均摊复杂度就是边数级别。

下面证明$SAM$边数级别是$O(n)$的:

为了能存下所有子串,$SAM$中一定要能遍历到每一个后缀。

任意求出$SAM$的一个生成树,边数级别是$O(n)$。

找到一条路径:根节点$\rightarrow$状态$A\rightarrow edge(A,B)\rightarrow$状态$B\rightarrow$结束状态(某个叶子节点)

其中$edge(A,B)$不一定存在,就加上这条边。这是我们会发现:这条路径恰好是遍历了一个后缀。

那么对于每个后缀我们都找出来一条这样的路径,每条路径最多加$1$条边,也保证了每个后缀都能遍历到,总边数级别就是$O(n)$的。

所以第一个$while$均摊是$O(n)$的。

    memcpy(son[sp],son[p],sizeof son[sp]);

如果$k$是常数大小的话,这个就是常数级别的。

如果$k$很大开了$map$的话,首先根据引理$4$,$SAM$节点个数是$O(n)$的。如果使一次复制达到$O(n)$级别,就必须至少有$O(n)$的节点,也就是插入了$O(n)$的字符。而一个点最多被复制一次,复杂度还是$O(n)$的。

    while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];

一个点同一个儿子最多被改变一次。换句话说,每条边最多被修改一次。

点$q$分裂出了点$sp$,把所有$son(p,c)==q$都转移到$sp$上。而$sp$本身由于赋值它的长度len[sp]=len[p]+1,所以当访问到点$sp$时,会按照$case\ 2$处理,连向它的边也不会再改变。总复杂度就是$O(n)$的。

PS:网上证明我太蒻了都没看懂,只能自己$yy$出这个证明。$wavwing$说这个证明的复杂度上界是不严格的,我证明的复杂度是和边数同级的,但据说应该是和点数同级。虽然都是$O(n)$的,但实际上效率会更好(通俗点说常数会更小)。反正能证出来就行


广义SAM

这部分可以先跳过去。

栗子

现在我们来$yy$一道题:

给多个模式串。多次询问,每次给定一个串,求在所有模式串中一共出现了几次。

根据后缀数组的经验,可以在每个模式串中间插入一个特殊字符$造$SAM$,出现次数就是到达节点的$siz$。

然而这里就有一个问题,比如给的串长度为$3$,走到的节点有一个串为:SAM$NB

这时候就出现问题了,因为是把串拼在一起的,就会受长度、特殊字符的影响,处理起来比较麻烦。(我太蒻了找不到很便捷的处理方式)

于是这时我们需要一只广义$SAM$。它可以存储每个串的所有子串,同时不会出现多余的像上面栗子那样的串

广义$SAM$网上找不到很详细的资料,一些原理和性质也没有系统的说明,所以我是纯粹背过的。

构造

其实构造贼简单,每插入一个串就把$last$赋值为$1$,其他和普通$SAM$一样。(至于为啥我也不知道啊)

可以用几个短串模拟一下构造。

以串$aab,bb,ab$为例,它长这个样子(还是$SAM\ Drawer$):

比普通$SAM$更丑了。。。

我们会发现里面有的点永远走不到,比如说点$5,8,9$。

至于怎么用。。。其实和普通$SAM$一样用就行。但是要注意的是广义$SAM$不能通过拓扑序求$siz$。

复杂度未知。。。


应用

以下用$edge(i,j)$表示$fa[j]=i$

求出每个点的siz​

$endpos$集合大小就相当于子串出现次数,求出这个就能乱搞干很多事情了。

$DP$求解。$fa$建出$parent\ tree$,按拓扑序或$dfsDP$。

方程:若点$i$不包含原串前缀,$siz[i]=\sum\limits_{edge(i,j)}siz[j]$;否则$siz[i]=1+\sum\limits_{edge(i,j)}siz[j]$

什么意思呢?首先对于不包含前缀的点我们分割它的$endpos$集合有了$parent\ tree$,它的儿子的并集就是它自己。

看到$parent\ tree$,可以发现集合$\{1,2,4,6\}$分割成了$\{2\}$和$\{4,6\}$,$\{1\}$去哪儿了?

分割集合相当于给集合里的每个串前添加字符得到新子串,产生了新的$endpos$等价类,分割下去。但是前缀不能在前面添加字符(它已经到头了),就不会分割出新的$endpos$等价类。显然一个类中最多只有一个前缀,就有上面的方程。

实现:只需要在$insert$函数第二行加一句:siz[ne]=1,建好$SAM$,$DP$就行啦。

关于拓扑序有个有点意思的求法:

    int tax[maxn],cur[maxn];    
    for(register int i=1;i<=cnt;++i)++tax[len[i]];
    for(register int i=1;i<=n;++i)tax[i]+=tax[i-1];
    for(register int i=1;i<=cnt;++i)cur[tax[len[i]]--]=i;

很像后缀排序里的基数排序,搞完这些之后$cur$里就是拓扑序啦。

如果想求出$endpos$集合里具体元素,珂以用线段树合并或$Splay$启发式合并,貌似主席树也行。

广义$SAM$不能通过拓扑序求$siz$

定位子串

给定一个字符串$S$,多次询问,给定$l,r$,求$S[l,r]$对应节点。

$parent\ tree$上父子都是后缀关系。预处理出所有前缀$r$对应的节点,倍增跳到$len$合适的地方。

判断子串

给一个模式串判断是否是母串的子串。

直接扔到$SAM$上跑一遍没到空节点上就是子串。

不同子串个数

由于$SAM$的最小性,同一个子串不会对应两条路径。所以就是求$SAM$上的路径数。

$DP$求解。$f(i)$表示点$i$出发的子串个数,方程$f(i)=\sum f(son(i,j))+1$,答案为$f(1)$。

也可以直接求$\sum len(i)-len(fa[i])$

不去重字典序第k小子串

后缀自动机经典应用。

先把$siz$求出来。

设$f(i)$表示从点$i$出发能得到的子串数量(可以重复)。

方程$f(i)=\sum\limits_{son(i,j)}siz(j)+f(j)$

然后从根节点开始,从小到大枚举字符,如果$k>f(son(i,j))+siz[son(i,j)]$就减去,否则走这条边并让$k-=siz[son(i,j)]$,$k$小于$0$就结束。

最长公共子串

给定2个模式串,求它们的最长公共子串。

当然用SA啊

对第一个串造$SAM$,用第二个串在$SAM$上跑,维护一下当前长度。依次匹配每一个字符,能走就走,长度++;不能走就不断向上跳$fa$,直到有边能走,长度置为该节点的$len$。中间过程所有到达的长度最大值为答案。

扩展到多个串上:

对第一个串造$SAM$,每个节点维护已匹配过的串走到该节点的最小长度$mi$当前串走到该节点最大长度$ma$。让每个串往上面跑,每次走到某个节点都用当前长度对$ma$取$\max$,跑完一个串逐步更新每个节点,$mi_i$对$ma_i$取$\min$,$\min\{ma_i,len[fa[i]]\}$对$ma_{fa[i]}$取$\max$。答案为$\max\{mi_i\}$。

最长公共后缀

给定母串,求两个前缀的最长公共后缀。

它们的$LCA$的$len$。

至于为啥。。。刚从$R2$回来好累啊懒得想了。

后缀的最长公共前缀倒过来就行了。

最小表示法

给定一个串,可以任意把最后面的字符移到开头,求能得到的字典序最小的串。

这不最小表示法、后缀数组SB题吗

把串复制一遍接在后边造$SAM$,就要找一条长度为$n$的字典序最小的路径。设$f(i)$为以节点$i$为起点,沿着$son$走能走的最长路的长度,$DP$求解,方程:$f(i)=\max\{f(son(i,j))+1\}$。

从根节点开始$dfs$,记录当前剩余未填字符数为$m$,从小到大枚举字符,如果$f[son(i,j)]+1\ge m$就走,直到$m$为$0$。

$A$了后看了看$asuldb$的题解发现我在瞎扯。。。

因为我们是把串循环同构了,所以从根节点出发一定有长度为$n$的路径,其他点同样有满足条件的路径。所以没必要$DP$,贪心走最小的儿子走$n$遍就完了。


水题

一些题在学后缀数组时已经做过啦,所以有的我是在口胡。。。

好多题目都是从asuldb那里偷过来的$QwQ$

【模板】后缀自动机

求出$endpos$集合大小,答案就是$max\{siz[i]len[i]\}(siz[i]>1)$

玄武密码

很裸的判断子串。。。

(我把这个题放上来好像显得很low)

弦论

填上我后缀数组的坑。
$t=0$,后缀数组随便做所有点的$siz$都是$1$,(同一个状态只出现一次),和上面应用一样跑就行啦。

$t=1$,还是上面那个。

生成魔咒

有了$SAM$这个题就很板子了,毕竟$SAM$就是在线的。

直接用式子$ans=\sum len(i)-len(fa(i))$,连$fa$时算上贡献就完了。

字符集太大了得上$map$。

SubString

询问答案就是在$SAM$上跑一遍到达的节点的$siz$,所以就是动态维护$siz$。

$siz$和$parent\ tree$有关,加字符有可能改变$fa$关系,$LCT$维护子树大小就好啦。

题解

熟悉的文章

关于怎么做。。。这里空太小了写不开

题解

Standing Out from the Herd

题解

碱基序列

动态规划。设$f(i,j)$表示前$i$组序列,有多少种方案走到节点$j$。

定义函数$walk(j,S)$表示从节点$j$出发走串$S$到达的节点。

刷表法,把母串$SAM$造出来。对于第$i$组序列的每个模式串$S$,都有转移$f(i+1,walk(j,S))+=f(i,j)$

答案为$\sum\limits_{i=1}^{cnt}siz[i]*f(k,i)$

复杂度$O(n\sum|S|)$

(题目数据范围不给清楚。。。模式串的长度总和应该不大,反正能过)

DNA

一开始想到了$dfs$、$bfs$和$DP$做法,不过十分怀疑复杂度。

对于$DP$,对$S_0$造$SAM$,设$f(i,j,k)=0/1$为匹配了$S$的前$i$位,已经有$k$位不同,是否能到达节点$j$。答案为$\sum siz[j] (f(n,j,0/1/2/3)=1)$

这时发现我们只关心最终是否能到达某个节点,状态就为$f(i,j)$表示匹配了$S$的前$i$位,到达节点$j$最少有多少位不同。

转移时枚举当前节点的下一位为$A,C,G,T$,和$i+1$位不同就加$1$。复杂度是$O(n^2)$的。

然后会发现实际上能转移的状态并不多,中间$f$值大于$3$的都可以舍弃掉了。可以结合一下$bfs$,开一个队列把有用状态装进去更新$f$。

因为有用的状态数不多好像$dfs$效率也不错。

Security

题解

Cool Slogans

题解

事情的相似度

简单概括:$[l,r]$中的前缀两两之间最长公共后缀的最大值。

先转成$LCA$。

平衡树维护$endpos$,启发式合并,把$siz$小的平衡树中每个$endpos$查一下大树里的前驱后继,也就是最可能有贡献的点对,它们的$LCA$为当前点,就有$n\log n$个三元组$(endpos_1,endpos_2,len[i])$,然后就是数点问题了。

你的名字

题解


下面是一些广义$SAM$的题。

前面熟悉的文章Standing Out from the Herd也是可以用广义$SAM$做的,而且应该比普通$SAM$更方便(不过当时没学)

Forensic Examination

比较裸的题了。

对母串和所有串造广义$SAM$,在上面跑一下母串,求出每个位置到达的节点(也就是$S[1,r]$到的节点)

然后线段树合并求出每个节点包含了哪些模式串及出现次数。

对于每个询问,从节点$S[1,p_r]$倍增向上跳到节点$S[p_l,p_r]$,求线段树中$[l,r]$的最大值就好啦。

把广义$SAM$造出来,统计一下每个节点属于多少个模式串(就是统计个颜色),这个线段树合并、$dsu\ on\ tree$都行。

对于每个串,我们统计其每个前缀的后缀的答案。前缀到达的节点容易找到,然后倍增跳到第一个颜色数$\ge k$的节点,$len$就是该前缀的贡献。

诸神眷顾的幻想乡

以每个叶子节点为根$dfs$一遍,相当于把这棵树看作以该节点为根的$trie$树,把这棵$trie$树上的串插到广义$SAM$里(广义$SAM$有一种标准的造法是以$trie$树造$SAM$,然而我懒得学了)。我们对每个节点存一下它的$last$,某个节点就根据它父亲的$last$插入进$SAM$。最后和普通$SAM$一样统计本质不同的子串就行了。因为一个点度数不超过$20$,复杂度是$OK$的。

看起来感觉这个做法很假。


然而它就是对的。。。