字符串，太抽象！
前置知识
- 自动机
一些约定
若无特殊说明，以下默认字符串下标从 \(1\) 开始。
引入
在做字符串题的过程中，我们经常需要对一个字符串的所有子串做一些事情，但是直接暴力做是 \(\mathcal{O}(n^2)\) 的，非常慢。
于是有些毒瘤跳了出来，说：“我们能不能造出一个能够接受一个字符串 \(S\) 的所有子串的自动机，满足状态数和转移数都是 \(\mathcal{O}(n)\) 的呢？”
于是，SAM（Suffix Automaton）就这么诞生了。
基础想法
由于子串就是后缀的前缀，并且自动机天生就能接受一个串的所有前缀，那么我们就只需要能够接受所有的后缀就行了。
很不幸，直接暴力把后缀丢进 Trie 里复杂度是 \(\mathcal{O}(n^2)\) 的，我们需要优化。
可以发现对于一些状态，我们是可以合并的，具体的，对于两个状态，如果它们的入边和出边都是一样的，那么这两个状态就可以被合并。
但是按照这种规则进行合并构造 SAM，复杂度依旧是 \(\mathcal{O}(n^2)\) 的，没有改善。我们需要一些更强大的工具来帮助我们。
\(\text{endpos}\) 与 \(\text{endpos}\) 等价类
对于一个字符串 \(S\)，我们定义它的一个子串 \(a\) 的 \(\text{endpos}\) 为 \(a\) 在 \(S\) 中所有的出现位置。例如，对于字符串 \(S=\mathtt{abcabb}\)，\(\text{endpos}(\mathtt{ab})=\{2,5\}\)。
定理 1.1：对于两个子串 \(a,b\)，设 \(|a|\le|b|\)：
- 若 \(a\) 是 \(b\) 的后缀，则 \(\text{endpos}(b)\subseteq\text{endpos}(a)\)；
- 否则，\(\text{endpos}(b)\cap\text{endpos}(a)=\varnothing\)。
证明：对于第一种情况，由于对于任何位置，只要 \(b\) 出现了，\(a\) 就一定会出现，故 \(\text{endpos}(b)\subseteq\text{endpos}(a)\)；对于第二种情况
对于一系列 \(\text{endpos}\) 相等的子串，我们把它们统称为一个 \(\text{endpos}\) 等价类。
例如，对于 \(S=\mathtt{abab}\)，由于 \(\text{endpos}(\mathtt{ab})=\text{endpos}(\mathtt{b})=\{2,4\}\)，因此我们认为 \(\mathtt{ab}\) 和 \(\mathtt{b}\) 属于同一个 \(\text{endpos}\) 等价类。
标签：子串,SAM,text,笔记,学习,endpos,字符串,mathtt From： https://www.cnblogs.com/bykem/p/17136964.html