对比

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