本文是《算法笔记》KMP算法章节的阅读笔记，文中主要内容来源于《算法笔记》。本文主要介绍了next数组、KMP算法及其应用以及对KMP算法的优化。
KMP算法主要用于解决字符串的匹配问题。即给定两个字符串text与pattern,需要判断pattern是否是text的子串。假设text的长度为n,pattern的长度为m,那么用暴力搜索的算法解决该问题需要的时间复杂度为O(m*n)。这种算法在m,n大于105级别是无法被接受。而KMP算法需要的时间复杂度仅为O(m+n)。Knuth、Morris、Pratt是发明这个算法的三位科学家。
1.next 数组
1.1 next数组定义
在学习KMP算法之前首先学习一下next数组。假设有一个字符串（下标从0开始）。next[i] 表示使该字符串的子串s[0···i]的前缀s[0···k]和后缀s[i-k···i]相等的最大k(k<i:前后缀可以重合但不能为整个子串)；如果找不到相等的前后缀组，那么next[i] = -1。
以字符串s = "ababaab"为例，其对应的next数组为[-1,-1,0,1,2,3,-1]。
当i = 0: 子串为"a"，找不到相等的前后缀（因为前后缀不能包含整个s[i])，因此next[0] = -1;
当i = 1: 子串为"ab"，找不到相等的前后缀，因此next = -1；
当i = 2: 子串为"aba"， k = 0时 "a" = "a"; k = 1时，"ab" != "ba";因此next[2] = 0;
依次类推可得到整个next数组。
1.2 next数组的计算
暴力求解next数组效率不高，下面介绍如何用“递推”的方式高效的求解next数组。即假设已经求出next[0]~next[i-1],使用它们的结果来快速得到next[i]。
为方便讨论，假设已知next[0] = -1 ; next[1] = -1 ; next[2] = 0; next[3] = 1,现在来求解next[4]。当得到next[3] = 1时，最长相等的前后缀为"ab"，之后在计算next[4]时，由于s[4] == s[next[3]+1]，故可将"ab"拓展为“aba”，即next[4] = next[3] + 1 = 2。
在此基础上计算next[5]。由于s[5] ! = s[next[4]+1],因此不能拓展。此时需要做的操作是缩短。希望能找到一个j，使得s[5] ==s[j+1]成立并满足s[0···j]是s[0···2]的一个后缀。同时为了满足相等的前后缀尽量长的目标，找到的j应该尽可能大。
很显然，只需要令j = next[2](找到"aba"的k),判断其是否满足s[5] ==s[j+1]：如果成立，next[5] = j + 1;如果不成立，就不断让j = next[j]，直到j回到-1，或是途中s[5] = = s[j+1]成立。在本例中，j = -1时满足条件，故next[5]=-1+1 = 0。
上述过程总结为一般算法描述为：
- 初始化next数组，令j = next[0] = -1;
- 让i 在1~len-1范围遍历（len为字符串s的长度），对每个i，执行3，4，以求出next[i];
- 不断让j = next[j]，直到j退回到-1，或是s[i] == s[j+1]成立；
- 如果s[i] == s[j+1]，则next[j] = j+1;否则next[i] = j。
代码实现如下：
//getNext 求解长度为len的字符串s的next数组
void getNext(char s[],int len){
int j = -1;
next[0] = -1; //init
for(int i = 1; i < len ; i++){ //求解next[1] ~ next[len - 1]
while(j != -1 && s[i] != s[j+1] ){
j = next[j];
}
if(s[i] == s[j+1]){
j++; //j指向next[i]
}
next[i] = j; } }
2.KMP算法
2.1 KMP算法实现字符串匹配
设有text = "abababaabc",pattern = "ababaab"，希望判断patten是否是text的子串。令i指向text的当前欲比位，令j指向patten中当前已被匹配的最后一位，这样只需要满足text[i]==pattern[j+1],就说明pattern[j+1]也被匹配成功，此时让i,j加1以继续比较；如果不满足text[i]==pattern[j+1],参见第一小节next数组的定义，只需令j = next[j],继续比较即可。在本例中，i指向text[4],j指向pattern[3],此时满足text[i] == pattern[j+1],故i,j加一继续匹配。当i指向text[5],j指向pattern[4]时不满足text[i] == pattern[j+1]匹配失败。令j = next[j] =2,此时满足匹配条件，故i,j均加一继续匹配。随后发现直至j==6均成功匹配，说明pattern是text的一个子串。
下面给出算法描述与代码实现：
- 初始化j = -1,j表示pattern当前已被匹配到的最后位;
- 让i遍历文本串text，对每个i,执行3，4来试图匹配text[i]和pattern[j+1]l
- 不断令j = next[j],直到j回退到-1，或是text[i]=pattern[j+1]成立;
- 如果text[i] == pattern[j+1],则令j++。如果j达到m-1,说明pattern是text的子串，返回true。
1 //KMP算法 判断pattern是否是text的子串
2 bool KMP(char text[],char pattern[]) {
3 int n = strlen(text); m = strlen(pattern);
4 getNext(pattern,m); //计算pattern的next数组
5 int j = -1;
6 for(int i = 0; i < n; i++){
7 while(j != -1 && text[i] != pattern[j+1]){
8
9 j = next[j]; //j回退使得满足条件或回到原点
10 }
11 if(text[i] == pattern[j+1]){
12 j++; //匹配成功，j指向已匹配的最后一位
13
14 }
15 if(j == m-1){
16 return true; //已全部匹配完成
17 }
18
19 }
20 return false; //匹配结束，失败
21
22 }
可以发现，求解next数组的过程其实就是模式串pattern进行自我匹配的过程。故上述代码与求解next数组的代码极为类似。
2.2 KMP算法实现统计出现次数
每次成功匹配统计次数的变量加1，成功匹配之后i = i+1,j 回退使得pattern[j+1] == text[i]。直接贴代码：
1 //KMP算法 统计pattern在text出现的次数
2 bool KMP(char text[],char pattern[]) {
3 int n = strlen(text); m = strlen(pattern);
4 getNext(pattern,m); //计算pattern的next数组
5 int j = -1,ans = 0;
6 for(int i = 0; i < n; i++){
7 while(j != -1 && text[i] != pattern[j+1]){
8
9 j = next[j]; //j回退使得满足条件或回到原点
10 }
11 if(text[i] == pattern[j+1]){
12 j++; //匹配成功，j指向已匹配的最后一位
13
14 }
15 if(j == m-1){
16 ans++;
17 j = next[j];
18 }
19
20 }
21 return ans;
22
23 }
2.3 时间复杂度分析
for语句循环了n次，复杂度为O(n)。在每一个for循环内，j要么自增1，要么减小。由于减小到最低为-1。所以while循环对于整个过程最多循环n次,平均每次是O(1)。因此可认为for语句的时间复杂度为O(n)。考虑到计算next数组需要O(m)的时间复杂度（用同样的分析方法），因此KMP算法总共需要O(m+n)的时间复杂度。