跳转至

对比

\(n\) 表示 模式串长度模式串长度之和\(m\) 表示 文本串长度

预处理 / 插入 匹配 空间 类型
KMP \(O(n)\) \(O(m)\) \(O(n)\) 超串结构
ACAM \(O(n\Sigma)\) \(O(m)\) \(O(n\Sigma)\) 超串结构
Trie \(O(n)\) \(O(n\Sigma)\)\(O(m)\) \(O(n\Sigma)\) 子串结构
SAM \(O(m\Sigma)\) \(O(n)\) \(O(m\Sigma)\) 子串结构
SA \(O(n\log n)\) \(O(n)\)
exKMP \(O(n)\) \(O(n)\)
Manacher \(O(n)\) \(O(n)\)

关键的注意点:ACAM,Trie,SAM 和字符集有关,只在字符集较小时可以使用。