KMP算法原理和代码实现
目录Contents
KMP算法主要解决的的是字符串匹配问题。 给定一个文本串T和一个模式串P,要求在文本串中找到模式串出现的位置。
引入:普通暴力匹配算法
最简单的字符串匹配算法是暴力匹配算法。其基本思想是:从文本串T的第一个字符开始,依次与模式串P的字符进行比较。如果遇到不匹配的字符,则将模式串向右移动一位,继续比较,直到找到匹配的位置或者文本串被扫描完为止。
1int BFSearch(string T, string P) {
2 int tsz = T.size();
3 int psz = P.size();
4 int t = 0; // T的指针
5 int p = 0; // P的指针
6 while (t <= tsz - psz && p < psz) {
7 if (T[p + t] == P[p]) {
8 p++;
9 } else {
10 t++;
11 p = 0;
12 }
13 }
14 if (p == psz) return t;
15 return -1;
16}这种算法的时间复杂度达到了O(m*n),其中m是文本串的长度,n是模式串的长度。为什么会出现这样的时间复杂度呢?考虑下面的例子:
1T = "AAAAAAAAAAAAAB"
2P = "AAAAB"当两个字符串出现大量重复字符的时候,BF算法会反复回溯模式串的指针,导致时间复杂度上升。 而KMP算法通过计算最大前后缀匹配长度,避免了这种回溯,从而提高了匹配效率。
KMP算法原理
如果我们不想直接把指针回溯到零,我们应该如何确定回溯的长度呢? 观察下面的例子:
1 012345678
2T = "ABCABCABD"
3 ^
4P = "ABCABD"
5 ^可以看到,当我们匹配到T[5]和P[5]时发生了不匹配。但是我们注意到,在P和T已经匹配过的部分中,P[0,2]和T[3,5]是相同的字符串"ABC"。而P[0,2]又是P[0,4]的前缀,T[3,5]与P[0,4]的后缀相同。这样,我们只需要将模式串P向右移动2位,继续比较。
1 012345678
2T = "ABCABCABD"
3 ^
4P = "ABCABD"
5 ^这样,我们可以看到两个指针后续的字符串是相同的,继续逐个比较字符即可匹配成功。
这说明我们可以利用已经匹配成功的部分来避免不必要的比较。具体来说,我们需要找到模式串P的前缀和后缀的最长匹配长度,这样当发生不匹配时,我们可以将模式串向右移动相应的位数,避免重新匹配前面已经匹配过的部分。
这个最长匹配长度可以通过一个辅助数组next来存储。next[j]表示模式串P的前缀P[0..j-1]中,既是前缀又是后缀的最长子串的长度。
算法实现
先不考虑计算next数组,直接实现KMP匹配算法:
1int kmp(string T, string P) {
2 vector<int> next = computeNext(P); // 计算next数组
3 int pt = 0; // T的指针
4 int pp = 0; // P的指针
5 while (pt < T.size() && pp < P.size()) {
6 if (T[pt] == P[pp]) {
7 pt++;
8 pp++;
9 } else if (pp > 0) {
10 pp = next[pp]; // 利用next数组回溯P的指针
11 } else {
12 pt++;
13 }
14 }
15 if (pp == P.size()) return pt - pp; // 返回开始匹配的位置
16 return -1;
17}接下来实现计算next数组的函数:
定义:next[k] 表示模式串P[0,k-1]的最长前后缀匹配长度。
compare表示P[0,k-2]的最长前后缀匹配长度。
- 如果
P[k - 1] = P[compare],那么显然,next[k] = compare + 1(为什么不是next[k] = next[k - 1] + 1呢?) - 如果
P[k - 1] != P[compare],则需要将compare向前回溯。假设更短的前后缀长度为m + 1,这里1表示后缀的最后一个元素,即P[k - 1],那么需要满足前后缀相同的条件:P[0, m - 1] = P[k - m - 1, k - 2]。这样我们就把‘前后缀相等’这个要求向前递推了一位。假若这个时候前一位的前后缀存在匹配的情况,那么我们想要从匹配好的后缀中进一步取出长度为m的后缀,这个取出的‘子后缀’必然和匹配好的前缀的相应‘子后缀’相同,即P[compare - m, compare - 1]=P[k - m - 1, k - 2](这是因为匹配的前后缀相同,所以它们相应位置的子串也相同);同时,这个‘子后缀’还必须和整个P[0, k - 1]的长度为m的前缀相等,也就是上面写的条件。这样,我们发现了一个巧妙之处:P[compare - m, compare] = P[0, m - 1],这表明m正是P[0, compare]的前后缀最大匹配长度!而P[0, compare]的最长前后缀匹配长度为next[compare],因此我们可以将compare更新为next[compare],如果满足条件1,则返回,否则继续,直到找到匹配或者compare为0。因此,前面不能简单地写成next[k] = next[k - 1],因为next[k - 1]表示的是P[0, k - 2]的最长前后缀匹配长度,而我们需要的是在不匹配时,模式串指针应该回溯到的位置。
1vector<int> computeNext(string P) {
2 if (P.size() < 2) return {0};
3 vector<int> next(P.size(), 0);
4 int compare = 0;
5 int cur = 2;
6 while (cur < P.size()) {
7 if (P[cur - 1] == P[compare]) {
8 compare++;
9 next[cur] = compare;
10 cur++;
11 } else if (compare > 0) {
12 compare = next[compare];
13 } else {
14 next[cur] = 0;
15 cur++;
16 }
17 }
18 return next;
19}总结
- 前后缀最大匹配长度有两层含义:一是表示前后缀的最大匹配长度,二是表示在发生不匹配时,模式串指针应该回溯到的位置。
- next求取时,分两种情况讨论,匹配和不匹配。不匹配时需要回溯compare指针,直到找到匹配或者compare为0。
- KMP算法的时间复杂度为O(m + n),其中m是文本串的长度,n是模式串的长度。相比于暴力匹配算法,KMP算法在处理大量重复字符时表现更优。
参考例题:Leetcode 28. find the index of the first occurrence in a string
2026年1月3日。
gitalk --repo Huaji-tye2007/MyBlog-Comments