标签：总结 SAM 后缀 算法 endpos 字符串 自动机 节点
KMP
AC 自动机 ACAM
exKMP Z 函数
manacher
后缀自动机 SAM
结论与思考
- 一个节点 \(i\) 到根节点的链上所有节点 endpos 的并集是以 \(i\) 为结尾的所有字符串（以 \(i\) 为结尾的后缀）。
- 节点 \(i\) 的 endpos 里所有后缀的出现次数相等，且儿子的 endpos 里的字符串长度一定大于父亲的长度。
- 节点 \(i\) 里所有节点各自的出现次数为 \(cnt_i\)。\(cnt_i\) 可以通过树形 dp 后求出。
- SAM 上匹配到一个节点后，可以不断删除要匹配的字符串的开头，当长度小于等于父亲的 \(longest\) 时移动到父节点即可。因为节点 \(i\) 存的是以 \(i\) 为结尾的后缀。
- 一个等价类，即一个节点 \(i\) 中字符串的个数为 \(len_i-len_{fa_i}\)。
- SAM 上从根节点到任意节点的路径是原串的一个子串，原串的一个子串也一定能用某条从根节点出发的路径表示。
- SAM 最多只有 \(2n-1\) 个节点， \(3n-4\) 条边。
- SAM 的转移边构成一个 DAG。
- 父节点的 endpos 集合一定包含了子节点的 endpos 集合。注意 endpos 集合存的是出现位置的末尾。
实现
- SAM 具体树形 dp 可以用桶排序代替，实现更小的常数。
后缀数组 SA
回文自动机 PAM
标签：总结,
SAM,
后缀,
算法,
endpos,
字符串,
自动机,
节点
From： https://www.cnblogs.com/zhr0102/p/18671696