通俗易懂的KMP算法详解
一：什么是KMP算法？
KMP诞生背景：
KMP(Knuth-Morris-Pratt)三位大佬联名提出，故以他们姓名的首字母命名，不得不说，他们的贡献巨大，因为在计算机的世界，子串模式匹配的场景非常多，越是底层的地方，其运行的性能越是重要。在KMP算法问世之前，其实在子串匹配上采用的都是暴力匹配，我们一般称之为朴素算法，可能是因为算法比较容易想到吧，所以很朴素。
朴素匹配算法：
假设称主串为str，模式串为ptr，如果采用暴力匹配，那其实就是将str和ptr逐个字符进行比较，如果匹配失败了，就将str后移一个位置，然后在进行逐一比较，考虑一下最差情况的时间复杂度达到了(str.length-ptr.length)*ptr.length。显然这是一种较差的算法。
朴素匹配算法.png
下面给出一下实现代码吧，就当为KMP算法预预热：
public class NaiveMatchingString {
/**
* 字符串匹配算法，简单易理解的就是暴力匹配，但是时间复杂度较高
*/
/**
*
* @param str:主串
* @param ptr:用于匹配的模式串
* @return 返回的是ptr匹配上str的时候，str的第一个字符所在字符串的位置，如果匹配不上
* 则返回0
*/
public int NaiveMatch(String str,String ptr){
int str_index = 0;// 表示匹配str所在的脚标
int str_move_index; // 表示匹配ptr过程中移动的脚标
int ptr_index;// 表示匹配ptr所在的脚标
for (str_move_index = str_index;str_index<=str.length()-ptr.length();str_index++,str_move_index++){
for (ptr_index = 0;str.charAt(str_move_index) == ptr.charAt(ptr_index);ptr_index++,str_move_index++){
if (ptr_index == ptr.length()-1){return str_index;}
}
str_move_index = str_index;
}
return 0;
}
public static void main(String[] args) {
String str = "dabxabxababxabwabxad";
String ptr = "abxabwabxad";
NaiveMatchingString naiveMatchingString = new NaiveMatchingString();
System.out.println(naiveMatchingString.NaiveMatch(str,ptr)); // 9
}
}
二：KMP算法核心解决了什么问题？
子串匹配.png
回想一下朴素匹配算法，当ptr和str进行逐一比较时，一旦中间哪一个不匹配了，str只是往后移动了一个位置，KMP算法核心就是根据ptr(模式串)匹配中str的部分求得最大的前后缀，然后根据这个可以获得str(主串)往后最大可以移动几个位置。从而可以节约时间复杂度。
举个简单的例子：
kmp1.png
如上图，第一次匹配str(1)=d,ptr(1)=a，所以不匹配，即str++，第二次匹配一直匹配到str(7)!=ptr(6)，按照朴素匹配的方式，继续将str++，但是仔细观察一下ptr匹配中str的部分，即abxab，如果只是简单的str++,那么第三次开始比较时ptr(2)=b,明显不会等于a。既然我们已经从之前匹配中的字符串当中可以看出一些信息，那么就不需要那么死板的暴力匹配了，那么该如何移动str的位置呢？回到abxab这个字符串当中，其前缀包含(a,ab,abx,abxa),不包含最后一个字符，其后缀为(b,ab,xab,bxab)不包含第一个字符，最大的公共前后缀是ab，这说明了啥，说明了可以这样子移动，见下图：
kmp2.png
从这里就可以了解到，KMP算法主要是解决以下问题：
1：通过观察之前匹配中的字符串，求出最大公共前后缀，使得str往后移动不是渐增，避免不必要的比较操作。
三：next数组怎么求？
上述只是针对匹配中的字符串abxab的一种解释，可以想象一下，在ptr和str匹配的过程当中，匹配中的字符串存在的可能性有多少种，是不是ptr含有多少元素就有多少种，而且每种都存在唯一的最大公共前后缀，其实求解这个的过程，就是求解著名的next数组，能够把这个理解了，KMP算法也就理解了八八九九了，next数组里面存放的是最大公共前后缀的长度，其决定了str每次往后移动的位置个数。
next数组.png
接下来对这副图进行一定的解释：
- i值表示匹配中ptr字符串的下标，比如只匹配中a，下标为0。
- 最右边的next[i]值，其实就是我们最终要求得的next数组，每个结点存放的是k值，k值可以理解为匹配中字符串的最大公共子串，可以看到当i=0,1,2时，最大的公共前后缀都是0，因为没有。
- 解释一下k，i指针，i指针很简单，每次都指向字符串的最后，k指针初始下标为0，然后与i下标的值进行比较，如果相等，则k++，不相等了，就将当前k的值存入next数组就好。
- 进行比较时，k下标和i下标不相等，其实分为两种情况，第一种情况是第一次比较时相等的，当k++以后(可能存在多次)，在比较可能存在不相等，这种情况直接将当前的K值存入next数组就好，还有一种情况，就是第一次比较都不相等，这种情况需要将k = next[k-1]，为什么这么操作，稍后解释。获取新的k值以后，再次进行与i比较，跟上述流程一样，这里需要注意的是，当k=0了，并且第一次比较就不相等，那么next[i]直接等于0了。
-
解释一下为什么当k!=0时，第一次比较就不相等要让k=next[k-1]，观察下图：
kmp3.png
假设当i=9时，这时k=4，最大公共前后缀是abxa，这个abxa的最大最后缀是a，并且k指针现在指向b。然后当i=10时，i指针指向d，由于k指针指向b，b!=d，这时候是会触发我们刚才说的表达式k=next[k-1]，这样子，k=1，即指向b，可能这时候就有疑问为什么不指向a，要指向b，仔细想想，当i=9时，k指针指向b，b不等于i指针指向的a，所以导致其最大公共前后缀只有4长度，如果相等了，那么长度就是5了。而且abxa的最大公共前后缀是a，那么就可以说明k指针指向的位置b肯定也不会等于i=10时的第一个字符a，因为它是abxa的最大公共前后缀。所以求k的表达式是k=next[k-1]，这是有讲究的。
求解next数组代码：
/**
* 获取next数组，KMP算法的核心。
* 主要步骤如下：
* 1、next数组的大小为ptr.length
* 2、每次计算最大前后缀的范围为0-next的下标
* 3、创建两个指针，一个为k指针，一个为i指针，用比较对应下标位置的字符是否一致
* 4、如果ptr.CharAt(k) == ptr.CharAt(i)，则k++，如果非第一次比较不相等，则k等于++后的值
* 5、如果第一次比较就不相等则k = next[k-1],然后继续执行与i下标的比较
* 6、一直循环至next[ptr.lenth-1],next数组存放的是k的值
*
* @param ptr
* @return
*/
public int[] getNext(String ptr) {
int K = 0; //初始化K指针
int I; // I指针始终指向最后的位置
int nextIndex = 1; //表示计算那个next脚标的数据,因为next[0] = 0，从1开始计算
int[] next = new int[ptr.length()];
next[0] = 0;
for (; nextIndex < ptr.length(); ) {
String substring = ptr.substring(0, nextIndex + 1);
I = substring.length() - 1;
if (substring.charAt(K) == substring.charAt(I)) {
while (K < substring.length() / 2 && substring.charAt(K) == substring.charAt(I)) {
K++;
}
next[nextIndex++] = K;
} else {
if (K == 0){
next[nextIndex++] = 0;
}else{
K = next[K - 1];
continue;
}
}
}
return next;
}
四：KMP算法实现
public class KMPStringMatching {
/**
* KMP算法：一种效率匹配子串的算法
*/
/**
* 获取next数组，KMP算法的核心。
* 主要步骤如下：
* 1、next数组的大小为ptr.length
* 2、每次计算最大前后缀的范围为0-next的下标
* 3、创建两个指针，一个为k指针，一个为i指针，用比较对应下标位置的字符是否一致
* 4、如果ptr.CharAt(k) == ptr.CharAt(i)，则k++，如果非第一次比较不相等，则k等于++后的值
* 5、如果第一次比较就不相等则k = next[k-1],然后继续执行与i下标的比较
* 6、一直循环至next[ptr.lenth-1],next数组存放的是k的值
*
* @param ptr
* @return
*/
public int[] getNext(String ptr) {
int K = 0; //初始化K指针
int I; // I指针始终指向最后的位置
int nextIndex = 1; //表示计算那个next脚标的数据,因为next[0] = 0，从1开始计算
int[] next = new int[ptr.length()];
next[0] = 0;
for (; nextIndex < ptr.length(); ) {
String substring = ptr.substring(0, nextIndex + 1);
I = substring.length() - 1;
if (substring.charAt(K) == substring.charAt(I)) {
while (K < substring.length() / 2 && substring.charAt(K) == substring.charAt(I)) {
K++;
}
next[nextIndex++] = K;
} else {
if (K == 0){
next[nextIndex++] = 0;
}else{
K = next[K - 1];
continue;
}
}
}
return next;
}
/**
*
* @param str:主串
* @param ptr:模式串
* @return
*/
public int getStrIndex(String str,String ptr){
//先获取模式串的next数组
int[] next = getNext(ptr);
int str_index = 0; //表示匹配主串的位置
int str_move_index; //表示匹配主串中移动的位置
int ptr_index; //表示匹配模式串中的位置
for (;str_index<=str.length()-ptr.length();){
for (ptr_index = 0,str_move_index = str_index;ptr.charAt(ptr_index) == str.charAt(str_move_index);ptr_index++,str_move_index++){
if (ptr_index == ptr.length()-1){
return str_index;
}
}
//获取新的str_index值
int ne;
if (ptr_index == 0){
ne = 0;
str_index++;
}else{
ne = next[ptr_index -1];
if (ne == 0){
str_index++;
}else{
str_index = str_index + (ptr_index - ne);
}
}
}
return 0;
}
public static void main(String[] args) {
String str = "dabxabxababxabwabxad";
String ptr = "abxabwabxad";
KMPStringMatching kmpStringMatching = new KMPStringMatching();
int strIndex = kmpStringMatching.getStrIndex(str, ptr);
System.out.println(strIndex); //9
}
}
kmp4.png
