第19章：字符串中查找子串出现次数——KMP算法原理与实现

各位同学，今天我们来聊一个经典话题——KMP算法。

说到字符串匹配，很多人第一反应就是暴力法。两个循环，一个遍历主串，一个遍历子串，匹配不上就回溯。简单粗暴，但效率嘛……说实话，我在早期做文本处理工具时，就吃过这个亏。当时要在一个几十MB的日志文件里查找某个模式串出现的次数，暴力法跑起来，那叫一个慢。用户等得不耐烦，直接关掉了程序。

从那以后，我就认真研究起了KMP。今天，我就把这块硬骨头给大家啃透了。

19.1 为什么需要KMP？

先看一个简单例子。

主串：ABABABCABABABCABABABC
子串：ABABABC

暴力法怎么做的？从主串第一个字符开始，逐个比较。匹配到第7个字符时发现不匹配，然后回溯到主串第2个字符，重新开始比较。

你想想看，这中间有多少重复劳动？

我举个例子。假设子串是AAAAAB，主串是AAAAACAAAAAB。暴力法在匹配到第5个字符时发现A和C不匹配，然后回溯到主串第2个字符，重新比较。实际上，我们已经知道前4个字符都是A，为什么还要重新比较？

这就是KMP要解决的问题——利用已经匹配的信息，避免不必要的回溯。

19.2 KMP算法的核心：next数组

KMP的精髓，就是next数组。它记录了子串中每个位置之前的子串的最长相等前后缀长度。

什么叫前后缀？

拿子串ABABABC来说：

• 前缀：从开头开始的子串，比如A、AB、ABA、ABAB……
• 后缀：从结尾开始的子串，比如C、BC、ABC、BABC……

最长相等前后缀，就是前缀和后缀中，长度最大且相等的那个子串。

举个例子：

• 子串ABAB：前缀有A、AB、ABA；后缀有B、AB、BAB。相等的前后缀是AB，长度2。
• 子串ABABA：前缀有A、AB、ABA、ABAB；后缀有A、BA、ABA、BABA。相等的前后缀是A和ABA，最长的是ABA，长度3。

next数组的值，就是每个位置之前子串的最长相等前后缀长度。注意，next[0]通常设为-1，表示没有前缀。

我习惯用下面这个表格来理解：

位置i	0	1	2	3	4	5	6
子串字符	A	B	A	B	A	B	C
next[i]	-1	0	0	1	2	3	4

怎么算出来的？

• i=0：没有前缀，next[0] = -1
• i=1：子串A，没有相等前后缀，next[1] = 0
• i=2：子串AB，没有相等前后缀，next[2] = 0
• i=3：子串ABA，前缀A等于后缀A，长度1，next[3] = 1
• i=4：子串ABAB，前缀AB等于后缀AB，长度2，next[4] = 2
• i=5：子串ABABA，前缀ABA等于后缀ABA，长度3，next[5] = 3
• i=6：子串ABABAB，前缀ABAB等于后缀ABAB，长度4，next[6] = 4

19.3 KMP匹配过程

有了next数组，匹配就变得简单了。

我们用两个指针i和j，分别指向主串和子串的当前位置。

1. 如果主串[i] == 子串[j]，则i++，j++
2. 如果匹配失败（主串[i] != 子串[j]）：
   • 如果j == 0，则i++（子串第一个字符就不匹配，直接移动主串指针）
   • 否则，j = next[j]（子串指针回溯到next[j]位置，主串指针不动）
3. 如果j == 子串长度，说明匹配成功，记录位置，然后j = next[j]继续查找

这里有个关键点：主串指针i从不回溯。这就是KMP高效的原因。

我画了一张流程图，帮助大家理解：

19.4 代码实现

好了，理论讲完了，咱们直接上代码。这是我个人习惯的写法，清晰易懂：

#include <stdio.h>
#include <string.h>

// 计算next数组
void getNext(const char *pattern, int *next) {
    int len = strlen(pattern);
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < len - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// KMP查找子串出现次数
int kmpCount(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m == 0) return 0;
    if (n < m) return 0;
    
    int next[m];
    getNext(pattern, next);
    
    int i = 0, j = 0;
    int count = 0;
    
    while (i < n) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        
        if (j == m) {
            count++;
            j = next[j];  // 继续查找下一个匹配
        }
    }
    
    return count;
}

int main() {
    char text[] = "ABABABCABABABCABABABC";
    char pattern[] = "ABABABC";
    
    int count = kmpCount(text, pattern);
    printf("子串 \"%s\" 在主串中出现了 %d 次\n", pattern, count);
    
    return 0;
}

优化后的getNext函数：

void getNextOptimized(const char *pattern, int *next) {
    int len = strlen(pattern);
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < len - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            // 优化：如果pattern[i] == pattern[j]，则next[i] = next[j]
            if (pattern[i] != pattern[j]) {
                next[i] = j;
            } else {
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

19.5 复杂度分析

指标	暴力法	KMP
时间复杂度	O(n*m)	O(n+m)
空间复杂度	O(1)	O(m)

n是主串长度，m是子串长度。KMP的时间复杂度是线性的，这在处理大文本时优势非常明显。

19.6 避坑指南

我曾经在项目中踩过一个坑，分享给大家：

有一次，我需要在一个二进制文件中查找某个模式串。我直接用KMP去匹配，结果发现匹配结果不对。后来排查了半天，才发现问题出在strlen上——二进制数据里可能包含\0字符，而strlen遇到\0就停了。

所以，处理二进制数据时，一定要用长度参数，而不是依赖字符串结束符。

另外，还有几个常见问题：

• next数组越界：当j回溯到-1时，要正确处理，否则会访问非法内存。
• 空子串：如果子串为空，直接返回0，不要进入匹配逻辑。
• 重叠匹配：如果要统计重叠出现的次数（比如AAA在AAAA中出现3次），匹配成功后j要回溯到next[j]，而不是直接置0。

19.7 实际应用场景

KMP的应用场景其实挺多的：

• 文本编辑器中的查找功能：比如在VS Code里按Ctrl+F，底层用的就是类似KMP的算法。
• 日志分析工具：从海量日志中提取特定模式的行。
• DNA序列匹配：生物信息学中，经常需要在长序列中查找短序列。
• 网络入侵检测：在数据包中匹配恶意特征码。

说实话，KMP虽然经典，但在实际工程中，如果模式串很短（比如长度小于10），暴力法反而更快，因为KMP需要额外计算next数组。我一般会在模式串长度大于20时，才考虑用KMP。

好了，关于KMP算法，今天就讲到这里。记住，理解next数组的生成过程，是掌握KMP的关键。多画图，多手动模拟几次，你就能彻底搞懂它。

---

公众号:蓝海资料掘金营，微信deep3321