后缀自动机

参考资料

• 后缀自动机 (SAM) - OI Wiki

简介

后缀自动机（Suffix Automaton，SAM）是能接受一个字符串所有后缀的最小确定有限自动机。它的每个状态对应一组 $\operatorname{endpos}$（结束位置集合）相同的子串，状态数与转移数都是 $O(n)$，可在线 $O(n)$ 构建。

借助 $\operatorname{parent}$ 树（按 $\operatorname{endpos}$ 的包含关系）与各状态的 $\operatorname{len}$，SAM 能高效解决本质不同子串计数、子串出现次数、两串最长公共子串等问题。

例题

洛谷 P3804 【模板】后缀自动机（SAM）

给定一个仅含小写字母的字符串 $s$，在所有出现次数不小于 $2$ 的子串中，求「出现次数 $\times$ 子串长度」的最大值。