- 什么是KMP算法？
- KMP 与 BF（暴力解法）的区别
- 附图
- KMP 的 遍历 子串变量 j 的 回退机制
- 练习（加深 求 next 数组 的印象）
- 练习一
- 练习二
- 接下来，又是推理时间: 如何用程序去 求 k值 / 求 next 数组的元素
- Java 实现 KMP 算法
- 附图 （讲解重要部分）
- 附图 1（主串 查找 子串的过程）
- 附图 2 （next数组，实现注意情况）
- C 实现 KMP 算法
- KMP算法优化 》》 next数组优化 》》 又称 nextval 数组
- 练习
- 文章至此就结束了，希望大家通过这封 KMP 信，能收获颇丰!
KMP 算法是一种改进的字符串匹配算法/ 找子串的算法的改进，由D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特 - 莫里斯 - 普拉特操作（简称 KMP算法），KMP算法的核心是利用匹配失败后的信息，尽量减少 模式串 和 主串 的匹配次数以达到快速匹配的目的、具体实现就是通过一个next()函数实现（其实更准确的来说是一个next数组），函数本身包含了 模式串/子串 的 局部匹配信息。KMP算法的时间复杂度O(M+N)[1]。 ——来自百度百科
KMP 与 BF（暴力解法）的区别
KMP 和 BF 唯一不一样的地方在：
当给你一个主串 和 模式串/子串，要你来查找主串是否包含子串，包含就返回 主串中子串的起始的位置，
现在用来遍历主串的变量 i 和 遍历子串的 变量 j，指向字符不匹配时，就意味着 目前 主串中 匹配的字符串 与 子串不相等，也就是说：目前从主串的某一种位置开始，一直到匹配字符不相等的位置之间，与子串不匹配。
KMP ：我主串的 i 并不会回退，并且 j 也不会回到下标0的位置。（这个就是接下来要搞懂的东西）
BF： 我主串的 i 回退 原来 匹配开始的位置，并加一，而 子串的 j 直接回到 下标为0 的 位置，然后继续匹配。
附图
KMP 的 遍历 子串变量 j 的 回退机制
到这里就不用翻了哦，因为截图，达到了最大限度，所以我不得不将其分割成两部分，希望不会影响到大家。
练习（加深 求 next 数组 的印象） 练习一
练习二
接下来，又是推理时间: 如何用程序去 求 k值 / 求 next 数组的元素
Java 实现 KMP 算法
public class Manuscript {
public static int KMP(String str,String sub,int pos){
if (str == null || sub == null){
//不管是主串，还是子串为null，你都查找不了 子串 在 主串中的位置
return -1;// 此时返回返回-1 表示找不到，或者说无法查找
}
int lenStr = str.length();//获取主串的长度
int lenSub = sub.length();//获取子串的长度
if(lenStr == 0 || lenStr==0){
// 这种情况也不用去想，空字符串里面一个元素都没有，肯定也比不了！
return -1;
}
if (pos < 0 || pos > str.length()){
// 你规定查找位置不合法，如果不写，很可能会导致越界异常，导致程序终止
return -1;
}
int i = pos;// 从指定的 pos 位置，开始遍历 主串
int j = 0;// 遍历 子串
int[] next = new int[lenSub];// 创建一个 next数组，长度 与 子串一致
getNext(sub,next);// 得到next 数组
while(i < lenStr && j < lenSub){
if(j==-1 || str.charAt(i)==sub.charAt(j)){// 这就是主串 和 子串匹配成功的情况
// j == -1. 是为了处理i 和 j 指向字符不匹配的情况
// j 回退的时候，在next数组中，一直没有 p[j] == p[k]的情况出现
// j 回退到 -1 的情况，也就是没有相同的真子串情况 p[0]~ p[k-1] != p[j-k] ~ p[j-1]
// 另外 这个条件需要放在前面，放在后 charAt一读取，就会发生越界异常
i++;
j++;
}else{
j = next[j];
}
}
if (j >=lenSub){
return i-j;
}
// 主串 不包含 子串的情况，也就是 i 与 j 不匹配，j 一直在子串的下标0位置待命
// 即 j < lenSub
return -1;
}
public static void getNext(String sub,int[] next){
next[0] = -1;
next[1] = 0;
int j = 2;// 提前走了一步
int k = 0;
while(j< sub.length()){// 遍历 子串
// p[j] == p[k]
if(k== -1 || sub.charAt(j-1) == sub.charAt(k)){
next[j] = k + 1;
j++;
k++;
}else {// p[j] != p[k], j需要回退
k = next[k];
}
}
}
public static void main(String[] args) {
System.out.println(KMP("abababcabcdef","abcd",0));//7
System.out.println(KMP("abababcabcabcdef","abcdf",0));// -1
System.out.println(KMP("abababcabcabcdef","ab",0));//0
}
}
附图 （讲解重要部分） 附图 1（主串 查找 子串的过程） 附图 2 （next数组，实现注意情况）
C 实现 KMP 算法
#include#include #include #include void GetNext(char*sub, int* next, int lenSub) { next[0] = -1; next[1] = 0; int j = 2; int k = 0; while (j < lenSub) { if (-1 == k || sub[j - 1] == sub[k]) { next[j] = k + 1; k++; j++; } else { k = next[k]; } } } int KMP(char* str, char* sub, int pos) { assert(str&&sub);//判断 主串 和 子串是否为 NULL 指针 int lenStr = strlen(str); int lenSub = strlen(sub); if (lenStr==0 || lenSub==0) { return -1; } if (pos < 0 || pos >= lenStr) { return -1; } int* next = (int*)malloc(sizeof(int)*lenSub); assert(next);// 判断空间是否开辟失败 GetNext(sub, next,lenSub); int i = pos; int j = 0; while (i < lenStr && j < lenSub) { if (-1 == j || str[i] == sub[j]) { j++; i++; } else { j = next[j]; } } free(next); if (j >= lenSub) { return i - j; } return -1; } int main() { printf("%dn", KMP("abababcabcdef", "abcd", 0));// 7 printf("%dn", KMP("abababcabcdef", "abcdf", 0));// -1 printf("%dn", KMP("abababcabcdef", "ab", 0));// 0 return 0; }
KMP算法优化 》》 next数组优化 》》 又称 nextval 数组
练习
如果 题目 规定了 next[0] 和 next[1] 的值， 也很简单，就按照这个模式就能写出来，如果运气好，题目规定 next[0] = 0; next[1] = 1，你就在我们这个结果的基础上加一就行了。
文章至此就结束了，希望大家通过这封 KMP 信，能收获颇丰!
