引入
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. 判断最长公共子串
最后的最后，学习一下高德纳：感谢你阅读本文，希望本文对你有用。
标签：子串,SAM,tree,算法,endpos,daduoli,节点,小记 From： https://www.cnblogs.com/BlackCrow/p/17673521.html