字符串后缀自动机（SAM）On this page后缀自动机（SAM）参考资料 后缀自动机（SAM） - OI Wiki 简介 后缀自动机（Suffix Automaton，SAM）是能接受一个字符串所有后缀的最小确定有限自动机。它的每个状态对应一组 endpos\operatorname{endpos}endpos（结束位置集合）相同的子串，状态数与转移数都是 O(n)O(n)O(n)，可在线 O(n)O(n)O(n) 构建。 借助 parent\operatorname{parent}parent 树（按 endpos\operatorname{endpos}endpos 的包含关系）与各状态的 len\operatorname{len}len，SAM 能高效解决本质不同子串计数、子串出现次数、两串最长公共子串等问题。 例题 Problemcode洛谷 P3804 【模板】后缀自动机（SAM）给定一个仅含小写字母的字符串 sss，在所有出现次数不小于 222 的子串中，求「出现次数 ×\times× 子串长度」的最大值。