对比

\(n\) 表示（模式串）字符串长度 或 字符串长度之和；\(m\) 表示文本串的长度。

	build 复杂度	匹配时间复杂度	空间复杂度	分类
KMP	\(O(n)\)	\(O(m)\)	\(O(n)\)	超串结构
Trie	\(O(n)\)	\(O(n\Sigma)\) 或 \(O(m)\)	\(O(n\Sigma)\)	子串结构
ACAM	\(O(n\Sigma)\)	\(O(m)\)	\(O(n\Sigma)\)	超串结构
SAM	\(O(m\Sigma)\)	\(O(n)\)	\(O(m\Sigma)\)	子串结构
SA	\(O(n\log n)\)		\(O(n)\) 或（st 表）\(O(n\log n)\)
exKMP	\(O(n)\)		\(O(n)\)
Manacher		\(O(n)\)	\(O(n)\)