字符串匹配：从朴素到高效的四重境界
字符串匹配，说白了就是在一个大字符串（主串）里找一个小字符串（模式串）。这问题看起来简单，但实际项目中坑不少。我早年做文本编辑器的时候，就因为这个功能没优化好，打开大文件直接卡死——嗯，从那以后我对字符串匹配算法就格外上心。
今天咱们一口气聊四种算法：朴素匹配、KMP、BM、Sunday。它们各有脾气，适用场景也不同。
一、朴素匹配：最直观，但最慢
朴素匹配的思路简单到令人发指：从主串的第一个字符开始，逐个字符跟模式串比较。如果匹配失败，就往后挪一位，继续比。
你想想看，这就像在一本书里找一句话，每次从当前页第一个字开始对，对不上就翻一页。最坏情况下，主串长度n，模式串长度m，时间复杂度O(n*m)。
// 朴素匹配
int brute_force(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == m) return i; // 匹配成功
}
return -1;
}
注意：朴素匹配虽然慢，但代码简单、不易出错。我在做嵌入式固件升级时，模式串长度通常不超过10个字符，用朴素匹配完全够用。别盲目追求高级算法，先看场景。
二、KMP算法：用next数组避免回溯
KMP的核心思想是：匹配失败时，模式串不一定要从头开始。它利用一个next数组，记录模式串中前后缀的重复信息，从而跳过一些已经比较过的位置。
举个例子：模式串"ABABAC"，当匹配到最后一个C失败时，前面"ABABA"其实已经匹配上了。这个子串的前缀"ABA"和后缀"ABA"相同，所以模式串可以直接跳到第三个字符继续比，主串指针不用回退。
next数组怎么算？我习惯用递推法：
void get_next(const char *p, int next[]) {
int m = strlen(p);
next[0] = -1;
int i = 0, j = -1;
while (i < m - 1) {
if (j == -1 || p[i] == p[j]) {
i++; j++;
next[i] = j;
} else {
j = next[j];
}
}
}
核心要点：KMP的时间复杂度是O(n+m)，主串指针永不回溯。这在处理流式数据时特别有用——比如从串口接收数据，边收边匹配，不用缓存整个主串。
不过说实话，KMP在实际工程中用得不算多。为什么？因为它的next数组计算有点绕，而且对于短模式串，朴素匹配已经够快。我个人只在模式串长度超过50、且匹配失败频繁的场景下才用KMP。
三、BM算法：从右向左匹配，坏字符+好后缀
BM算法是另一种思路：从模式串的末尾开始往前匹配。一旦发现不匹配，利用两个规则决定跳多远：
- 坏字符规则：主串中那个不匹配的字符，如果在模式串中没出现过，直接跳过整个模式串长度；如果出现过，跳到该字符在模式串中最后一次出现的位置。
- 好后缀规则：已经匹配的后缀部分，如果在模式串前面出现过，可以跳过去复用。
BM算法在实际文本搜索中表现极佳，平均时间复杂度接近O(n/m)。我记得在做一个日志分析工具时，用BM算法替换了原来的朴素匹配，处理速度提升了近10倍。
// BM算法核心：坏字符跳转表
void generate_bc(const char *p, int bc[]) {
int m = strlen(p);
for (int i = 0; i < 256; i++) bc[i] = -1;
for (int i = 0; i < m; i++) bc[(unsigned char)p[i]] = i;
}
int bm_search(const char *text, const char *pattern) {
int n = strlen(text), m = strlen(pattern);
int bc[256];
generate_bc(pattern, bc);
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && text[i + j] == pattern[j]) j--;
if (j < 0) return i;
// 坏字符规则决定跳转
i += j - bc[(unsigned char)text[i + j]];
}
return -1;
}
小技巧：BM算法的坏字符表只针对ASCII字符集。如果是Unicode文本，需要调整。我曾经踩过这个坑——处理UTF-8编码的中文时，直接按字节建表会出问题。
四、Sunday算法：比BM更简单的跳跃
Sunday算法是BM的简化版。它关注的是主串中参与匹配的最后一个字符的下一个字符。如果这个字符在模式串中没出现，直接跳过整个模式串长度+1；如果出现过，跳到该字符在模式串中最后一次出现的位置。
你想想看，Sunday算法比BM少了一个"好后缀"规则，实现起来清爽很多。而且在实际测试中，Sunday算法的平均性能往往不输BM。
// Sunday算法
int sunday_search(const char *text, const char *pattern) {
int n = strlen(text), m = strlen(pattern);
int shift[256];
for (int i = 0; i < 256; i++) shift[i] = m + 1;
for (int i = 0; i < m; i++) shift[(unsigned char)pattern[i]] = m - i;
int i = 0;
while (i <= n - m) {
int j = 0;
while (j < m && text[i + j] == pattern[j]) j++;
if (j == m) return i;
if (i + m >= n) break;
i += shift[(unsigned char)text[i + m]];
}
return -1;
}
五、四种算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 特点 | 推荐场景 |
|---|---|---|---|---|
| 朴素匹配 | O(n*m) | O(1) | 简单直观 | 短模式串、嵌入式 |
| KMP | O(n+m) | O(m) | 主串不回溯 | 流式数据、长模式串 |
| BM | O(n/m)平均 | O(m+256) | 从右向左、跳跃大 | 大文本搜索 |
| Sunday | O(n/m)平均 | O(256) | 实现简单、跳跃大 | 通用场景 |
六、知识体系图
七、避坑指南
我曾经在实现KMP的next数组时，把next[0]设成了0而不是-1，结果匹配逻辑全乱套。后来查了半天才发现——next[0] = -1 是约定，表示第一个字符就不匹配时，主串指针前进一位。
还有一次，我用BM算法处理二进制数据，坏字符表按256字节建没问题，但模式串里如果包含0x00，建表时要注意：shift[0]不能设成-1，否则会死循环。嗯，这个坑我印象很深。
Sunday算法看起来简单，但要注意：当模式串最后一个字符在主串中对应的下一个字符不存在时（即i+m >= n），要立即终止，否则会越界。
总结一句话：没有银弹。朴素匹配适合短串，KMP适合流式数据，BM和Sunday适合大文本。选哪个，取决于你的主串长度、模式串长度、以及字符集大小。我个人的习惯是：先上Sunday，不行再换BM，KMP留着面试用。
公众号:蓝海资料掘金营，微信deep3321