对比
\(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 和字符集有关,只在字符集较小时可以使用。