字符串不会一点

每次讲字符串杂题都发现自己忘光了。

本文章用于我个人字符串专题重生。

二分+哈希

咕

AC 自动机

咕

SAM

说文解字 : SAM = Suffix AutoMation（后缀自动机）

即一个可以表示字符串所有后缀的自动机。具体的，一个 SAM 是一个有一个确定的源点和不同终止节点的有向无环图。同时，SAM 是一个在线构造的自动机。即每次添加一个字符。我们可以通过将从源点走向终止节点的路径上的边（转移）对应的字符拼起来得到字符串所有的后缀。

显然的，由于我们每次走一条边得到了所有的后缀，我们在走边的过程中也一定走了所有的后缀的所有前缀。因此 SAM 中也包含了字符串的所有子串。这也使得它非常强大。

endpos

我们在这里要引入一个概念叫 \(\text{endpos}\) 集合。

我们规定，\(S\) 一个子串 \(T\) 在 \(S\) 中所有出现位置的终止位置的集合。

• 在 aabab 中子串 \(\text{endpos}(\text{ab}) = \{3,5\}\)

试探究一下这玩意的性质，发现：

• 若子串 \(S'\) 为子串 \(S\) 的一个后缀，那么一定有 \(\text{endpos}(S) \subseteq \text{endpos}(S')\)

• 不妨设 \(|S| < |T|\) 则 \(\text{endpos}(S)\) 与 \(\text{endpos}(T)\) 有交 \(\Longleftrightarrow\) \(S\) 是 \(T\) 的一个后缀。

• 

• 对于一个 \(\text{endpos}\) 集合 \(S\)，发现所有 \(\{|T|,\text{endpos}(T) = S\}\) 连续不重复。且把它们按长度排序，前一个是后一个的后缀。

• 将所有子串按照它们的 \(\text{endpos}\) 集合分为若干等价类。考虑拎出一个等价类中长度最大的子串 \(S\)，则可以发现 \(S\) 前加上任意一个字符都会转移到另外一个 \(\text{endpos}\) 等价类。根据前面的推导，发现 \(\text{endpos}(S') \subset \text{endpos}(S)\)。于是便构成了一个树形结构。

。