什么是后缀自动机 (SAM)？

后缀自动机（Suffix Automaton, SAM）是一个强大而精巧的数据结构，它能接受一个字符串 S 的所有后缀。更神奇的是，它实际上也接受了 S 的 所有子串。SAM 是一个既包含字符串所有子串信息，又具有最小节点和边数的有向无环图（DAG）。

对于一个长度为 n 的字符串，SAM 的空间复杂度和在线构建的时间复杂度都是线性的 O(n)。

核心概念

1. 状态 (State): SAM 中的每个节点代表一个状态，每个状态对应着原字符串中一个或多个子串的集合。
2. 转移 (Transition): 状态之间的有向边代表字符的转移。从状态 u 到 v 有一条字符 c 的转移边，表示在 u 所代表的子串集合中的所有字符串末尾添加字符 c 后，得到的新字符串都属于 v 所代表的子串集合。
3. 后缀链接 (Suffix Link): 这是 SAM 最核心的概念之一。每��非初始状态都有一个后缀链接，指向另一个状态。状态 u 的后缀链接指向状态 v，表示 v 所代表的子串集合是 u 所代表的子串集合中 所有字符串 的 最长后缀，且这些后缀也存在于 v 的子串集合中。所有后缀链接最终都会指向初始状态，形成一棵树状结构（Parent Tree）。

什么是 Manacher 算法？

Manacher 算法是一种用于在 线性时间内 找到字符串中最长回文子串的算法。传统的中心扩展法时间复杂度为 O(n²)，而 Manacher 算法通过利用回文串的对称性，避免了大量重复的比较，达到了 O(n) 的效率。

核心思想

Manacher 算法的核心在于维护一个 回文半径数组 p 和两个变量：

• p[i]: 以字符 i 为中心的回文串的半径长度。
• max_right: 当前已发现的所有回文串中，右边界能到达的最远位置。
• center: 对应 max_right 的那个回文串的中心位置。

什么是 AC 自动机？

AC 自动机（Aho-Corasick Automaton）是一种高效的、基于字典树（Trie）和 KMP 思想的字符串匹配算法。它能够在一个主文本串中，同时查找多个模式串的存在，且时间复杂度为线性 O(N+M)，其中 N 是主文本串长度，M 是所有模式串的总长度。

核心思想

AC 自动机巧妙地结合了两种数据结构的优点：

1. Trie (字典树): 用来存储所有的模式串。Trie 的结构使得所有模式串共享公共前缀，节省了空间。
2. 失败指针 (Fail Pointer): 这是 AC 自动机的精髓，类似于 KMP 算法中的 next 数组。每个 Trie 节点都有一个失败指针。节点 u 的失败指针指向的节点 v，代表了从根到 v 的路径所形成的字符串，是“从根到 u 的路径所形成的字符串”的 最长真后缀，并且这个后缀本身也是一个模式串的前缀。

什么是 KMP 算法？

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主文本串 S 中查找一个模式串 P 的出现位置。它的核心优势在于，当匹配过程中发生不一致时，它能利用已经匹配过的信息，跳过一些不必要的比较，从而避免了暴力匹配中的指针回溯，将时间复杂度优化到线性 O(n+m)。

核心思想：next 数组

KMP 算法的精髓在于一个预处理过的 next 数组（有时也叫 lps 数组，表示最长公共前后缀 Longest Proper Prefix which is also Suffix）。next[i] 存储的是模式串 P 的子串 P[0...i] 中，最长的相等的前缀和后缀的长度。