KMP 算法

本节主要讨论字符串的匹配问题，也就是说，如果给出两个字符串 text和 pattern，需要判断字符串 pattern是否是字符串 text的子串。

一、next数组

next[i]表示使子串 s[0...i]的前缀 s[0...k]等于后缀 s[i-k...i]的最大的 k；如果找不到相等的前后缀，那么令 next[i] = -1。显然，next[i]就是所求最长前后缀中前缀最后一位的下标。

next数组的求解过程如下：

1. 1. 初始化next数组，令 j = next[0] = -1。
   2. 让 i在 1~len-1范围遍历，对每个 i，执行 3、4，以求解 next[i]。
   3. 不断令 j=next[j]，直到 j回退到 -1，或是 s[i] == s[j+1]成立。
   4. 如果 s[i] == s[j+1]，则 next[i] = j+1；否则 next[i] = j。

代码如下：

1 // 求解长度为len的字符串s的next数组
 2 void getNext(char s[], int len) {
 3     int i, j = -1;
 4     next[0] = -1;            // 初始化 j=next[0]=-1 
 5     for(i=1; i<len; ++i) {    // 求解 next[i]
 6         // 循环直到 j 回退到 -1，或是 s[i] == s[j+1] 成立 
 7         while(j != -1 && s[i] != s[j+1]) {
 8             j = next[j];
 9         }
10         if(s[i] == s[j+1]) {// 若 s[i] == s[j+1] 
11             j++;            // next[i] = j+1 
12         }
13         next[i] = j;         // 否则 next[i] = j 
14     }
15 }

二、KMP算法

以下为 KMP算法的一般思路：

1. 1. 初始化 j=-1，表示 pattern当前已被匹配的最后位。
   2. 让 i遍历文本串 text，对每个 i，执行 3、4来试图匹配 text[i]和 pattern[j+1]。
   3. 不断令 j = next[j]，直到回退为 -1，或是 text[i] == pattern[j+1]成立。
   4. 如果 text[i] == pattern[j+1]，则令 j++。如果 j达到 m-1，说明 pattern是 text的子串，返回true。

代码如下：

1 // 判断 pattern 是否是 text 的子串 
 2 int KMP(char text[], char pattern[]) {
 3     int n=strlen(text), m=strlen(pattern);    // 字符串长度 
 4     getNext(pattern, m);                    // 求 next 数组 
 5     int i, j = -1;
 6     for(i=0; i<n; ++i) {                    // 试图匹配 text[i] 
 7         while(j!=-1 && text[i]!=pattern[j+1]) {
 8             j = next[j];
 9         }
10         if(text[i] == pattern[j+1]) {
11             j++;                            // 匹配成功,j+1 
12         }
13         if(j == m-1) {                        // 完全匹配 
14             return 1;
15         }
16     }
17     return 0;
18 }

接下来考虑如何统计文本串 text中模式串 pattern出现的次数。代码如下：

1 // 统计 pattern 在 text 中出现的次数 
 2 int KMP(char text[], char pattern[]) {
 3     int n=strlen(text), m=strlen(pattern);    // 字符串长度 
 4     getNext(pattern, m);                    // 求 next 数组 
 5     int i, ans=0, j = -1;                    // ans 存储 pattern 出现的次数 
 6     for(i=0; i<n; ++i) {                    // 试图匹配 text[i] 
 7         while(j!=-1 && text[i]!=pattern[j+1]) {
 8             j = next[j];
 9         }
10         if(text[i] == pattern[j+1]) {
11             j++;                            // 匹配成功,j+1 
12         }
13         if(j == m-1) {                        // 完全匹配 
14             ans++;                            // 成功匹配次数 +1
15             j = next[j];                    // 继续匹配 
16         }
17     }
18     return ans;
19 }

完整测试代码如下：

1 /*
 2     KMP算法 
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 
11 #define maxn 100
12 int next[maxn]; 
13 
14 // 求解长度为len的字符串s的next数组
15 void getNext(char s[], int len) {
16     int i, j = -1;
17     next[0] = -1;            // 初始化 j=next[0]=-1 
18     for(i=1; i<len; ++i) {    // 求解 next[i]
19         // 循环直到 j 回退到 -1，或是 s[i] == s[j+1] 成立 
20         while(j != -1 && s[i] != s[j+1]) {
21             j = next[j];
22         }
23         if(s[i] == s[j+1]) {// 若 s[i] == s[j+1] 
24             j++;            // next[i] = j+1 
25         }
26         next[i] = j;         // 否则 next[i] = j 
27     }
28 } 
29 
30 // 统计 pattern 在 text 中出现的次数 
31 int KMP(char text[], char pattern[]) {
32     int n=strlen(text), m=strlen(pattern);    // 字符串长度 
33     getNext(pattern, m);                    // 求 next 数组 
34     int i, ans=0, j = -1;                    // ans 存储 pattern 出现的次数 
35     for(i=0; i<n; ++i) {                    // 试图匹配 text[i] 
36         while(j!=-1 && text[i]!=pattern[j+1]) {
37             j = next[j];
38         }
39         if(text[i] == pattern[j+1]) {
40             j++;                            // 匹配成功,j+1 
41         }
42         if(j == m-1) {                        // 完全匹配 
43             ans++;                            // 成功匹配次数 +1
44             j = next[j];                    // 继续匹配 
45         }
46     }
47     return ans;
48 }
49 
50 int main() {
51     char text[maxn], pattern[maxn];
52     while(scanf("%s %s", text, pattern) != EOF) {
53         // 输出匹配次数 
54         printf("ans=%d\n", KMP(text, pattern));
55     }
56 
57     return 0;
58 }

输入：

abababab abab

输出：