引入

daduoli最近对自己的名字很感兴趣，于是他开始研究自己的名字。知周所众，搞清楚一个字符串的最好方法就是把他的所有子串列出来（误），所以daduoli开始尝试列举他名字中所有的子串。

列了好一会，daduoli发现子串太多了，于是尝试把它们拼在一起。拼了好一会儿，他拼出来一个奇怪的东西。此时shui_dream路过：“你咋拼了个SAM？”

（以上故事情节纯属虚构，如有雷同，那就雷同）

算法原理

$trie$

事情还要从daduoli拼的过程说起。

daduoli打算先拿他的姓试试水（知周所众，daduoli姓daduo），他考虑将姓的所有的后缀放到一个 $trie$ 树上，它看起来是酱紫的：

发现这个 $trie$ 有许多非常好的性质：

有一个源点，若干个终止点。边代表在目前的字符串后加上的字母。从源点到任意一个节点的任意路径可以形成一个字符串
从源点到任意节点的任意路径能形成的字符串均为原串子串。从源点到任意节点的任意路径不能形成的字符串均不为原串子串（简单来说，这个图可以表示，且仅可以表示出原串的所有子串）
从源点到任意终止节点的任意路径形成的字符串均为原串后缀
从源点出发的任意两条不同路径形成的字符串不相同

虽然这个 $trie$ 能完美满足daduoli的要求，但daduoli并不满意，应为这棵树的节点数实在是太多了，最坏情况会是 $O(n^2)$ 的，如果daduoli名字在长个十倍的话，建出来的 $trie$ 对于密恐的daduoli来说就太恐怖了。

突然，daduoli发现了这个 $trie$ 是可以压缩的，他尝试压缩掉了一个点：

daduoli发现即使trie变成了一个DAG，他仍然能在上面找到所有的子串，于是daduoli开始思考如何把原trie压缩成一个点数尽可能少的DAG。

就在daduoli苦思冥想时，突然受到仙人托梦，醒了之后立刻就理解了一切（）

接下来让我们看看daduoli理解了什么：

（daduoli觉得自己的名字真不好拼，于是下两个小节的所有图片将描述字符串"$aababa$"。）

$endpos$

定义

对于原串的一个子串 $p$ ，$endpos(p)$ 的值为$p$在原串中出现的所有位置的右端点集合。举个栗子，对于串"daduo"而言，$endpos($"$d$"$)=\{1,3\}$ 。

结论1

\[\color{Red}结论1:如果两个子串的 endpos 相同，则其中子串一个必然为另一个的后缀 \]

设两个子串中较短的串为 $t$ ，较长的串为 $s$ ，用反证法假设两个子串的后$|t|$个字符中至少有一个不相同，但是因为两串的 $endpos$ 相同，所以这个假设恒为假。QED.

结论2

\[\color{Red}结论2:对于任意两个子串 t 和 p(|t|<|p|) ，[endpos(p) \in endpos(t)] xor [endpos(p) \cap endpos(t) = \varnothing] = 1 \]

结论1的逆命题，分类讨论 $t$ 为或不为 $p$ 的后缀即可。

定义：$endpos$ 等价类

$endpos$ 相同的两个子串归为一个 $endpos$ 等价类。

结论3

\[\color{Red}结论3:一个 endpos 等价类中的串长度连续 \]

由结论2可知，长度是连续的。并且任意的两个 $endpos$ 等价类不会包含同一个子串。

后面的推论会比较重要

结论4

\[\color{Red}结论4:endpos 等价类个数的级别为 O(n) \]

对于一个 $endpos$ 等价类（后文简称类），根据结论3，存在一个长度最长的串 $p$ ，在 $p$ 前添加一个字符使得字符串仍为原串的子串，得到的串 $t$ 必然不属于 $p$ 所在的类，并且由结论2我们可以知道该串的 $endpos(t)$ 必然是 $endpos(p)$ 的子集。

发现在 $p$ 前加的字符如果不同，设形成的子串分别为 $t_1$ 与 $t_2$ ，那么由结论2可知$endpos(t_1) \cap endpos(t_2) =\varnothing$。

由上面的两个小结论，我们就可以把“在 $p$ 前添加一个字符使得字符串仍为原串的子串”这个操作看做对 $endpos(p)$ 进行分割，割成若干 $endpos(t_x)$ 。这个操作像极了daduoli天天钻研的data structure：线段树。不难发现线段树这样二分的分割所产生的子集个数是最多的，但节点数也才堪堪 $2n-1$ ，所以类个数数量级为 $O(n)$ 。

后缀自动机

定义：$parent \enspace tree$

daduoli发现可以把等价类之间的分割表示成一棵树：

这样形成类与类之间父子关系的一棵树，就叫 $parent \enspace tree$ 。

结论5

\[\color{Red}结论5:一个类中，最短的子串长度等于其父亲最长子串+1 \]

其实证明早就在结论4第二个小结论的推导中便已给出。

这个结论结合结论2，我们就只需在 $parent \enspace tree$ 的节点保存该类的最长子串即可，其他子串都可以通过一步步去掉前缀直到父亲的最长子串长度$+1$ ，这样的 $parent \enspace tree$ 长这样：

定义：后缀自动机

后文简称后缀自动机为 $SAM$

在daduoli坚持不懈地拼字符串后，$SAM$ 终于是给他拼出来了。

$SAM$ 的节点是 $parent \enspace tree$ 中的节点，$parent \enspace tree$ 的根节点（即空串所在的类）是 $SAM$ 的源点，而终止节点则是整个原串所在类的节点以及该节点在 $parent \enspace tree$ 上的所有祖先。

虽然daduoli把 $SAM$ 的雏形给搞出来了，但仙人并没有告诉他怎么连边，也没有告诉他到底怎么用。正当daduoli感到疑惑时，shui_dream过来了，这才发生了开头的一幕。

（接下来是shui_dream的主场！）

shui_dream大手一挥，往daduoli的 $SAM$ 上连上好几条边，daduoli定睛一看，恍然大悟：

不难看出，沿着原 $parent \enspace tree$ 的边走，就是在串的前面加字符，而沿着非 $parent \enspace tree$ 的边走，则相当于在边的后面加字符。

发现 $SAM$ 完美满足本节开头所提到 $trie$ 的性质。前三个性质显然满足，对于最后一个，因为类是分割形成的，所以不同的类中不会包含同一个串，因此到任意两个不同节点所形成的字符串均不重复。接下来说明 $SAM$ 存在。

$SAM$ 的存在性取决于边的正确性，因此下面论证边的正确性。显然沿着 $parent \enspace tree$ 的边走是没有任何问题的，问题就是非 $parent \enspace tree$ 的边是否正确。对于一个类中的所有子串，在其后添加一个字符，他们一定在另一个相同的类中，所以非 $parent \enspace tree$ 的边也是正确的。从而 $SAM$ 存在。

更严谨的证明将会在后文提到，这里只是进行并不那么严谨的解释。

结论6

\[\color{Red}结论6:SAM$ 的边数为 $O(n) \]

又臭又长，直到有这个东西就行了，先不整了

~~反正写代码不考证明~~

构造

基本形态

daduoli非常想要卷学习 $SAM$ ，于是死皮赖脸地让shui_dream教他构造（说是要帮shui_dream代打舟游）。没有办法，shui_dream只能再次大手一挥，画了一张描述 $SAM$ 形态的图片：

daduoli根本看不懂，于是shui_dream解释道：下面整齐的一行表示各个前缀所属的节点。一个前缀显然是所属类中长度最长的，因为它前面不能再加字符了。相邻的两个前缀显然一定会连上非树边，但是不相邻的点之间也会有边，所以这些节点放在最下面，方便观察。

上方零散的点是不包含任意前缀的类，一些边连下来，一些边连上去，内部还有一些边。这就是 $SAM$ 的基本形态（结构）。

Code

~~我相信一定有人会直接跳到这看我丑陋的马蜂的（说的就是你Cust10）~~

“$SAM$ 的构造是在线的，相当于把原串拆成一个个字符，通过不断把字符塞进 $SAM$ 进行构造。”shui_dream这样说到。

突然，天上掉下来一个大大的代码框和链接，想必是daduoli认真学习的样子感动了仙人吧（）link：

点击查看代码

~~这种题就没必要放评测记录了吧……~~

即使有仙人所写的精美注释，daduoli看见这玩意一脸懵逼，~~（我也是）~~，于是旁边一脸轻松的shui_dream开始给daduoli一段段地讲解。

int p = pre, np = pre = ++cnt;
a[np].len = a[p].len+1;

在这段程序段中，$pre$ 表示未加入字符 $x$ 之前，整个串所属的节点编号，$cnt$ 则表示整个 $SAM$ 的节点总数。

加入了字符 $x$ 后，显然整个串的长度就变长了，因此需要新建一个节点 $np$ ，并且 $len(np) = len(p)+1$ 。

注意到在加入字符 $x$ 之后 $endpos$ 发生变化的串只有可能是新串的后缀，所以接下来就需要遍历每一个旧串的后缀，看看加上字符 $x$ 之后 $endpos$ 有没有变化。

for (; p && !a[p].ch[x]; p = a[p].fa) a[p].ch[x] = np;

这个语句其实就是上述操作，去遍历每一个旧串后缀，然后尝试加上字符 $x$ 。 p = a[p].fa 这个在 $parent \enspace tree$ 跳父亲的操作，就是在不断寻找更短的前缀。而如果这个节点有 $x$ 的出边，就说明之前有这个子串，不能把它丢到新的节点，这就是!a[p].ch[x]的意义。至于p只是为了防止自由奔放地跳出根节点。

if (!p) a[np].fa = 1;

如果说最后 $!p$ ，就说明新加的字符没有产生任何一个旧串中已有的子串。长度为 $0$ 的串 $+x$ 都不是旧串中的子串，说明 $x$ 是全新的字符，它的父亲就应该是空串。

int q = a[p].ch[x];
if (a[np].len == a[p].len+1) a[np].fa = q;

$x$不是新字符，那么某个旧串后缀就会有一个 $x$ 的出边。在第二节后缀自动机定义处有提到这样的边完全覆盖了整个类 $np$ ，因此如果它们的最长串之间的长度差为 $1$ ，说明它们之间只差了一个字符 $x$ ，直接将 $q$ 作为 $np$ 的父亲就好。

最后的最后，我们的daduoli把他的名字塞进了 $SAM$ 里，可喜可贺，可喜可贺。（daduoli：我只是想划水）

感谢daduoli与shui_dream的友情出演（）

应用

1. 判断子串

2. 不同子串个数

3. 所有子串中字典序第 $i$ 大的是哪个

4. 判断最长公共子串

最后的最后，学习一下高德纳：感谢你阅读本文，希望本文对你有用。

526互联

『算法小记』SAM

引入

算法原理

\(trie\)

\(endpos\)

定义

结论1

结论2

定义：\(endpos\) 等价类

结论3

结论4