C++字符串处理是算法竞赛中的半壁江山。从判断子串到模式匹配，从敏感词过滤到最长公共子串，你总会遇到这样的困惑：KMP 我会写，AC 自动机我学过，后缀数组好像也能做，但面对一道具体的字符串题，我到底该用哪一个？
选错算法，轻则多写几百行代码，重则 TLE 或 MLE。本文将从核心思想、时间复杂度、代码复杂度、适用场景四个维度，帮你彻底厘清 KMP、AC 自动机、后缀数组这三个经典字符串算法之间的关系与选择策略。无论你是竞赛选手还是面试准备者，这篇文章都能让你少走弯路。
一、KMP：单模式串匹配的王者 核心思想 KMP（Knuth‑Morris‑Pratt）算法解决的是 单模式串匹配 问题：给定一个文本串 S 和一个模式串 P，找出 P 在 S 中所有出现的位置。朴素匹配的复杂度为 O(|S|·|P|)，而 KMP 通过 前缀函数（π 数组） 或 next 数组 在匹配失败时避免回退文本串指针，将复杂度降至 O(|S|+|P|)。
前缀函数 π[i] 表示子串 P[0..i] 中真前缀与真后缀相等的最长长度。当字符失配时，我们可以根据 π 值跳跃到下一个可能匹配的位置。
C++ 实现（简洁版）
vector< int > build_prefix ( const string & p) {
int m = p. size ( ) ;
vector< int > pi ( m, 0 ) ;
for ( int i = 1 ; i < m; ++ i) {
int j = pi[ i- 1 ] ;
while ( j > 0 && p[ i] != p[ j] ) j = pi[ j- 1 ] ;
if ( p[ i] == p[ j] ) ++ j;
pi[ i] = j;
}
return pi;
} vector< int > kmp_search ( const string & s, const string & p) {
vector< int > pi = build_prefix ( p) ;
vector< int > res;
int j = 0 ;
for ( int i = 0 ; i < s. size ( ) ; ++ i) {
while ( j > 0 && s[ i] != p[ j] ) j = pi[ j- 1 ] ;
if ( s[ i] == p[ j] ) ++ j;
if ( j == p. size ( ) ) {
res. push_back ( i - j + 1 ) ;
j = pi[ j- 1 ] ;
}
}
return res;
}
适用场景 局限性 二、AC 自动机：多模式串的瑞士军刀 核心思想 AC 自动机（Aho‑Corasick Automaton）是 KMP 在多模式串上的推广 。它先将所有模式串构建成一棵 Trie 树，然后通过 失配指针（fail 指针） 在匹配失败时快速跳转到另一个状态。预处理复杂度 O(总模式串长度)，匹配复杂度 O(文本串长度 + 每个字符的跳转次数)，整体接近 O(文本长 + 所有模式串总长）。
失配指针 的设计非常像 KMP 的 π 数组，只不过从一维的链扩展到了树上的跨分支跳跃。构建时使用 BFS 逐层计算 fail 指针。
C++ 实现（结构体封装）
struct AhoCorasick { struct Node {
int next[ 26 ] ;
int fail;
int cnt;
Node ( ) {
memset ( next, 0 , sizeof ( next) ) ;
fail = cnt = 0 ;
}
} ;
vector< Node> trie;
AhoCorasick ( ) { trie. emplace_back ( ) ; }
void insert ( const string & s) {
int u = 0 ;
for ( char ch : s) {
int c = ch - 'a' ;
if ( ! trie[ u] . next[ c] ) {
trie[ u] . next[ c] = trie. size ( ) ;
trie. emplace_back ( ) ;
}
u = trie[ u] . next[ c] ;
}
trie[ u] . cnt++ ;
}
void build ( ) {
queue< int > q;
for ( int c = 0 ; c < 26 ; ++ c) {
if ( trie[ 0 ] . next[ c] ) {
trie[ trie[ 0 ] . next[ c] ] . fail = 0 ;
q. push ( trie[ 0 ] . next[ c] ) ;
}
}
while ( ! q. empty ( ) ) {
int u = q. front ( ) ; q. pop ( ) ;
for ( int c = 0 ; c < 26 ; ++ c) {
int v = trie[ u] . next[ c] ;
if ( v) {
trie[ v] . fail = trie[ trie[ u] . fail] . next[ c] ;
trie[ v] . cnt += trie[ trie[ v] . fail] . cnt;
q. push ( v) ;
} else {
trie[ u] . next[ c] = trie[ trie[ u] . fail] . next[ c] ;
}
}
}
}
int match ( const string & text) {
int u = 0 , res = 0 ;
for ( char ch : text) {
int c = ch - 'a' ;
u = trie[ u] . next[ c] ;
res += trie[ u] . cnt;
}
return res;
}
} ;
适用场景 局限性
构建和存储开销较大（每个字符对应一个节点，节点数组大小 ≈ 总模式串字符数 × 字母表大小）。
如果模式串数量很少（例如 1 个），用 AC 自动机属于“杀鸡用牛刀”，不如直接 KMP。
不能直接处理模式串之间的“重叠”计数细节（可通过拓扑排序或单独记录解决）。
三、后缀数组：全局视角的强大工具 核心思想 后缀数组（Suffix Array）是对字符串的所有后缀进行排序后得到的数组 sa[i] 表示排名第 i 的后缀的起始位置。通常配合 rank 数组（后缀的排名）和 height 数组（相邻排名后缀的最长公共前缀长度）使用。
后缀数组可以在 O(n log n) 或 O(n) 时间内构建（倍增法、DC3、SA‑IS），配合 LCP 可以解决一类“子串”相关问题：最长重复子串、不同子串个数、两个字符串的最长公共子串、模式串在文本中的出现次数（成功匹配次数可用二分 + LCP 在 O(|P| log n) 内得到）等。
C++ 实现（倍增法模板，简短版）
vector< int > build_sa ( const string & s) {
int n = s. size ( ) ;
vector< int > sa ( n) , rank ( n) , tmp ( n) ;
for ( int i = 0 ; i < n; ++ i) sa[ i] = i, rank[ i] = s[ i] ;
for ( int k = 1 ; k < n; k <<= 1 ) {
auto cmp = [ & ] ( int i, int j) {
if ( rank[ i] != rank[ j] ) return rank[ i] < rank[ j] ;
int ri = ( i + k < n) ? rank[ i + k] : - 1 ;
int rj = ( j + k < n) ? rank[ j + k] : - 1 ;
return ri < rj;
} ;
sort ( sa. begin ( ) , sa. end ( ) , cmp) ;
tmp[ sa[ 0 ] ] = 0 ;
for ( int i = 1 ; i < n; ++ i) tmp[ sa[ i] ] = tmp[ sa[ i- 1 ] ] + cmp ( sa[ i- 1 ] , sa[ i] ) ;
rank = tmp;
}
return sa;
}
更常用的是同时构建 height 数组：
vector< int > build_height ( const string & s, const vector< int > & sa) {
int n = s. size ( ) ;
vector< int > rank ( n) , height ( n) ;
for ( int i = 0 ; i < n; ++ i) rank[ sa[ i] ] = i;
int h = 0 ;
for ( int i = 0 ; i < n; ++ i) {
if ( rank[ i] == 0 ) continue ;
int j = sa[ rank[ i] - 1 ] ;
while ( i + h < n && j + h < n && s[ i+ h] == s[ j+ h] ) ++ h;
height[ rank[ i] ] = h;
if ( h) -- h;
}
return height;
}
适用场景
子串统计类问题 ：不同子串个数（ n*(n+1)/2 - sum(height)）。
最长公共子串 （两个或多个字符串）。
出现至少 k 次的最长子串 （通过 height 数组的滑动窗口）。
模式串匹配 ：如果仅需判断模式串是否出现，后缀数组 + 二分也能做，但通常不如 KMP 直接。唯一优势是预先建好后缀数组后，可以应对大量不同模式串的查询。
字符串周期性分析 。
局限性
代码复杂，调试困难，常数较大。
无法在线处理（需要预先知道整个文本）。
对于单纯的多模式串匹配，AC 自动机会更轻量。
四、三者对比表（一目了然） 五、选择决策树（照着做） 当你拿到一道字符串题时，按以下顺序提问：
是不是只需要在一个文本中查找一个模式串？ → 是：用 KMP 。简单高效，不易错。 → 否：进入下一问。
是不是需要同时查找多个模式串（比如字典中的单词）？ → 是：用 AC 自动机 。这是它的主场。 → 否：进入下一问。
问题是否涉及子串的排序、最长公共前缀、重复次数、不同子串个数等“全局统计”属性？ → 是：用 后缀数组 （或后缀自动机 SAM，如果是竞赛也可考虑）。 → 否：再检查是否能用哈希 + 二分或者更简单的做法（比如双指针）。
另外，还有一些特殊情况：
如果模式串集合 不固定 ，而是动态变化（例如允许插入删除），则 AC 自动机不合适，可能需要使用 Trie + fail 树 + BIT 离线处理，但这就更复杂了。
如果只是判断一个模式串是否在文本中出现，且文本长度巨大（1e7），模式串单次查询，哈希（滚动哈希 + 二分）可能比 KMP 更快（但哈希有碰撞风险）。
对于字符串 周期性 问题，KMP 的 π 数组可以直接给出循环节长度（ len - π[len-1] if len % (len-π[...]) == 0）。
六、实战决策案例 例子 1 ：洛谷 P3375 【模板】KMP 字符串匹配 → 明显的单模式串匹配，直接 KMP。
例子 2 ：洛谷 P3808 【模板】AC 自动机（简单版） → 多模式串匹配，统计出现次数，AC 自动机。
例子 3 ：洛谷 P3809 【模板】后缀排序 → 后缀数组模板，用于后续各类子串问题。
例子 4 ：给定一个字符串，求其不同子串的数量。 → 后缀数组 + height 数组，公式 n*(n+1)/2 - sum(height[i])。也可以用后缀自动机，但后缀数组足够。
例子 5 ：给定一个文本串 T 和 Q 个模式串，Q 很大（1e5），T 固定（1e5），要求判断每个模式串是否在 T 中出现。 → 用后缀数组 + 二分：对每个模式串，在 sa 上二分检查是否匹配。预处理 O(n log n)，每次查询 O(|P| log n)。如果模式串总长很大，也可以考虑构建 T 的哈希表做滚动哈希，但后缀数组更安全。
例子 6 ：给定一组单词，找出其中任何一个单词是否为另一个单词的前缀。 → 将单词插入 Trie 树（可不用 AC 自动机的 fail），直接遍历即可。
七、C++ 实现注意事项
KMP ：注意边界， pi 数组的含义以及失配时 j = pi[j-1]。
AC 自动机 ：节点数组用 vector<Node> 动态分配，避免静态数组大小难估算。 build() 中需要将不存在的 next 指针指向 fail 的对应转移，可以节省匹配时的循环。
后缀数组 ：倍增法实现中，对 pair 的排序可以用 std::sort，但常数较大。竞赛中常使用基数排序优化到 O(n)。如果追求简洁，可先写倍增 sort 版本（n ≤ 200000 能过）。
内存 ：后缀数组需要多个 vector<int>（sa, rank, height, tmp），每个 n+5 大小，1e6 级别下约 16MB，可以接受。
八、总结
单模式串匹配 → KMP
多模式串匹配 → AC 自动机
子串全局统计、LCP 相关 → 后缀数组
这三个算法不是互相替代的，而是各司其职。一个成熟的竞赛选手应该熟练掌握 KMP 和 AC 自动机，并至少能手写后缀数组的倍增版（或会用 std::sort 的版本）。遇到题目时，先分析问题类型，再按上述决策树选择工具。
字符串的世界远不止这些：后缀自动机（SAM）、Z 函数（扩展 KMP）、Manacher 等同样重要。但掌握了今天讨论的三种“顶梁柱”，你已经能应对 80% 的字符串题了。剩下的 20%，留给下一次的专题吧。
