“后缀数组好$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=\min\{mi_i,ma_i\}$，而如果存在$ma_i$，$fa[i]$必定能完全匹配，则$mi_{fa[i]}=len[fa[i]]$。答案为$\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$的。

前言