浅谈 KMP 算法
最近在复习数据结构，学到了 KMP 算法这一章，似乎又迷糊了，记得第一次学习这个算法时，老师在课堂上讲得唾沫横飞，十分有激情，而我们在下面听得一脸懵比，啥？这是个啥算法？啥玩意？再去看看书，完全听不懂呀？总之，觉得十分懵比，课后去看了一些视频和博客，才慢慢有一点理解，学习不是一蹴而就的，需要脚踏实地的努力。过了三年，重新温习这个算法，似乎依旧不是很明白，理解得不够透彻，重新拾起课本和视频，认真学习这个算法。
１.KMP 算法简介
KMP 算法是由三位老前辈（D.E.Knuth，J.H.Morris 和 V.R.Pratt )的研究结果，该算法巧妙之处在于避免重复遍历的情况，全称叫做克努特-莫里斯-普拉特算法，简称 KMP 算法，D.E.Knuth，编写了《计算机程序设计艺术》写完了第四卷，这部著作被誉为计算机领域中的“相对论”。
2.子串 next 数组的计算
KMP 算法关键点是先求出 next[] 数组，这个 next 数组只与模式匹配串有关，例如以 “abababca” 这个子串计算一下它的 next 数组
下标为 index = 0 开始 ,
index = 0 ，”a” 的前缀和后缀都为空集，value = 0；
index = 1，”ab” 的前缀和后缀分别为 “a” 和 “b”，不相等，value = 0；
index = 2， “aba” 的前缀是 “a”、 “ab”，后缀是 “ba”、”a”，有相同交集 “a”，长度为 1, value = 1；
index = 3， “abab” 的前缀是 “a”、”ab”、”aba”，后缀是 “bab”、”ab”、”b”，有最长相同交集 “ab”， 长度为 2，value = 2；
index = 4，”ababa” 的前缀是 “a”、”ab”、”aba”、”abab”，后缀是 “baba”、”aba”、”ba”、”a”，有最大相同交集 “aba”，长度为 3， value = 3；
index = 5，”ababab” 的前缀是 “a”、”ab”、”aba”、”abab”、”ababa”，后缀是 “babab”、”abab”、”bab”、”ab”、”b”，有最长相同交集 “abab”，长度为 4， value = 4；
index = 6，”abababc” 的前缀是 “a”、”ab”、”aba”、”abab”、”ababa”、”ababab”，后缀是 “bababc”、”ababc”、”babc”、”abc”、”bc”、”c”，没有相同交集，value = 0；
index = 7，”abababca” 的前缀是 “a”、”ab”、”aba”、”abab”、”ababa”、”abababc”，后缀是 “bababca”、”ababca”、”babca”、”abca”、”bca”、”ca”、”a”，有相同交集 “a”，长度为1，value = 1；
最后结果如下：
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
3、如何使用 next[] 数组
得到子串的 next 数组以后，在目标串中匹配使用 next 数组，通过使用 next 数组避免重复的匹配已经匹配过的元素，如果找到长度为 partial_match_length 的部分匹配，并且表 next [partial_match_length]> 1，我们可以提前跳过 partial_match_length – next[partial_match_length-1] 个字符
总结移动位数 = 已匹配的字符数 – 对应的部分匹配值
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
以 “bacbababaabcbab” 为例说明它的匹配过程，第一次匹配， 调到 index = 1 位置，如下
bacbababaabcbab
|
abababca
不难看出， 部分匹配的长度为 partial_match_length = 1， 但是在 next [ partial_match_length – 1] = 0，也就是 next[0] = 0，这个元素，所以我们不需要跳过任何元素，接下来 cb 和 a 都不匹配直接向右匹配，到了下一个 a 匹配的地方
bacbababaabcbab
| | | | |
abababca
来到这个地方，你会发现此时部分匹配的长度为 5 ， partial_match_length = 5， next[partial_match_length – 1] = next[4]，查 next 数组，next[4] = 3，这就意味着在接下来的匹配中我们要跳过 partial_match_length – next[partial_match_length-1] ，即 5 – next[4] = 5 – 3 = 2，要跳过 2 个字符，所以接下来的匹配应该变成了如下所示：
bacbababaabcbab
xx | | |
abababca
xx 表示跳过了，部分匹配长度为 3， partial_match_length = 3，next[partial_match_length – 1] = next[2] = 1，接下来匹配中要跳过
partial_match_length – next[partial_match_length – 1]， 即 3 – 1 = 2， 跳过 2 个字符后的匹配情况如下：
bacbababaabcbab
xx |
abababca
得到部分匹配长度为 1 ， partial_match_length = 1， next[partial_match_length – 1] = 0，接下来匹配不用跳过字符，向右匹配，匹配串比剩余的主串要长，所以没有找到匹配的字符串。
4、KMP 算法代码实现，使用 C 语言实现
#include <stdio.h> #include <stdlib.h> #include <string.h> void get_next(char T[],int next[])//next数组 { int i,j; i=0;//前 j=1;//后 next[1]=0; while(j<T[0]) { if(i==0 || T[i]==T[j]) { i++; j++; next[j]=i; /*if(T[i]!=T[j]) { next[j]=i; } else { next[j]=next[i]; }*/ } else { i=next[i]; } } } int Index_KMP(char S[],char T[]) { int next[1000]; int i=1; int j=1; get_next(T,next);//获得next数组 /* for(i=1;i<=T[0];i++) { printf("%d ",next[i]); } */ while(i<=S[0] && j<=T[0]) { if(j==0||S[i]==T[j]) { i++; j++; } else { j=next[j]; } } if(j>T[0]) return i-T[0]; return 0; } int main (){ char T[1000],S[1000]; int i,k; while(scanf("%s %s",S,T)!=EOF) { k=strlen(T); for(i=strlen(T);i>0;i--)//向后移动 { T[i]=T[i-1]; } T[0]=k; k=strlen(S); for(i=strlen(S);i>0;i--)//向后移动 { S[i]=S[i-1]; } S[0]=k; printf("%d\n",Index_KMP(S,T)); } return 0; }
运行结果如下：
4 为第一个出现匹配字符串的数字下标从 1 开始
5、个人总结
经过这次对于 KMP 算法的练习，使我重新练习了一遍，关于 KMP 中算法实现的某些步骤依旧不是很清楚，有些地方想得还不是特别明白，也许这就是差距。今天出现了一些代码的 Bug，为了解决 Bug 查了一些网站的资料，重新温习了 C语言的使用，今天过得很充实。
欢迎大家关注我的微信公众号：
参考资料：
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://liam.page/2016/12/20/KMP-Algorithm/
https://blog.dotcpp.com/a/8986