KMP算法学习（包含所有next数组的求解）
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的第一次出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。
所以kmp算法的关键也是next数组它指明了如果当前位置不匹配时的最佳回溯位置（而不是像普通暴力法一样永远从头开始）。
next数组与最长相等前后缀的长度有关，我们先从求解最长相等前后缀的长度开始：
前缀、后缀的定义：不包含首字母/尾字母的其余字母的组合
Eg：对于字符串"aabaa"为例
前缀集合{a, aa, aab, aaba, aaba} 后缀集合{a, aa, aab, aaba} 所以这个字符串的最长相等前后缀的长度就为5（两个集合中最长相等的）。
所以我们能够将一字符串的每一部分的最长相等前后缀长度求出，以"aabaac"为例：
val[i]数组是当前位置及之前位置的子串的最长相等前后缀长度。
next[i]数组是在出现不匹配的情况下的下一次匹配的回溯的位置。
当字符下标i从1开始时
i 1 2 3 4 5 6
str[i] a a b a a c
val[i] 0 1 0 1 2 0
next_1数组就可以通过val[]数组得到，next_0[i] = val[i - 1] + 1(i > 0, 初始化next_0[0] = 0)，大家先往下看之后会解释为什么
next_1[i] 0 1 2 1 2 3
当字符下标i从0开始时
i 0 1 2 3 4 5
str[i] a a b a a c
val[i] 0 1 0 1 2 0
next_1[i] 0 1 2 1 2 3
next_0数组的每一位都比next_1数组少1，也就是next_1[i] = val[i - 1] (i > 0, 初始化next_1[0] = -1)
next_0[i] -1 0 1 0 1 2
根据《数据结构 C语言版》上对于next[i]的归纳如下（当下标从1开始）：
0; 当i=1时
next_1[i] = k | max{s[1]...s[k-1] = s[i-k+1]...s[i-1]};//即能够匹配的最长前后缀长度 （当存在匹配的前后缀集合时）
1; 其他情况
下标从0开始时也可作如下归纳：
-1; 当i=1时
next_0[i] = k | max{s[0]...s[k-1] = s[i-k]...s[i-1]};//即能够匹配的最长前后缀长度（ 当存在匹配的前后缀集合时）
0; 其他情况
其实对于以上的val[]、next_0[]、next_1[]都是可以当作next[]的，下面会一一演示
以val[]作next数组
因为val记录的是最长相等的前后缀，我们可以通过这个来规避一些重复比较
index: 0 1 2 3 4 5 6 7 8
对于主串： a a b a a b a a c
模式串： a a b a a c
我们可以求出val[] 0 1 0 1 2 0i指向主串，j指向模式串
KMP算法的精髓就是i不回退，而暴力法的缺陷也是i频繁的回退导致的在比较下标为5的时候我们发现不匹配于是查出next[4](当前位的前一位)为2，所以我们令j=next[4]
当i=5,j=5时
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
i=5,j=2
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
我们发现[i]=[j]，所以接着往下比较（如果还不相同我们则再令j=next[j-1]）
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
比较到j=s2.length()就代表匹配成功了，返回开始下标i-j
当以next_0[]作next数组时
因为next_0[j]总等于val[j-1](i!=0, next_0[0] = -1),其实就相当于我们不需要向上面一样找next[j-1]了，直接用next[j]就行index: 0 1 2 3 4 5 6 7 8
对于主串： a a b a a b a a c
模式串： a a b a a c
我们可以求出val[] -1 0 1 0 1 2
在比较下标为5的时候我们发现不匹配于是查出next[5](当前位)为2，所以我们令j=next[5]
当i=5,j=5时
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
i=5,j=2
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
我们发现[i]=[j]，所以接着往下比较（如果还不相同我们则再令j=next[j]）
0 1 2 3 4 5 6 7 8
a a b a a b a a c
a a b a a c
|
比较到j=s2.length()就代表匹配成功了，返回开始下标i-j下面会给出这部分的讲解和代码
当以next_1作next数组时与以next_0的情况基本一致，只是下标差个1，大家可以自己按上面情况分析
代码部分：
val[i]的求解
//i是后缀的首位，j是前缀的末位 因为str默认从0开始所以j就初始为0
static void getNext3(String str, int[] next3) {
int j = 0;
for(int i = 1; i < str.length(); i++) {
// 当前字符和 j 指向的字符不相等，需要回溯
while(j > 0 && str.charAt(j) != str.charAt(i)) {
j = next3[j-1];
}
// 如果当前字符和 j 指向的字符相等，说明找到了更长的前缀后缀
if(str.charAt(i) == str.charAt(j)) {
next3[i] = ++j;
} else {
// 如果不相等，说明没有找到更长的前缀后缀，j 应该为 0
next3[i] = j;
}
}
} next[i]求解
//前两种是通过next[i]与val[i]的关系得出的
/*
(1). 设置一个固定指针指向i-1位置，一个移动指针j首先指向i-1。
(2). 如果第i-1个字符和第j位置next指向的字符相同，则设置next为j位置next值+1。
(3). 如果不相同则让j指针移动。移动到目前next指向的位置。直到第i-1个字符和j位置next指向的字符相同或者j位置next指向0，则设置next为j位置next值+1。
*/
//下标从1开始的next数组
static void getNext5(String str, int[] next5) {
next5[1] = 0;
next5[2] = 1;
for(int i = 3; i <= str.length(); i++) {
int j = i - 1;
while(next5[j] != 0 && str.charAt(i-2) != str.charAt(next5[j] - 1)) j = next5[j];
next5[i] = next5[j] + 1;
}
}
//下标从0开始的next数组
static void getNext4(String str, int[] next4) {
next4[0] = -1;
next4[1] = 0;
for(int i = 2; i < str.length(); i++) {
int j = i - 1;
while(next4[j] != -1 && str.charAt(i-1) != str.charAt(next4[j])) j = next4[j];
next4[i] = next4[j] + 1;
}
}
//下标从1开始的next数组，也是《数据结构 C语言版》上的求解方式
static void getNext3(String str, int[] next3) {
int i= 1, j = 0;
while(i < str.length()) {
if(j == 0 || str[i] == str[j]) {
i++, j++;
next[i] = j
} else {
j = next[j];
}
}
}通过以上求next的方式都是正确的至于该选择哪一种就看个人习惯了，现在我们来解释为什么next数组是这样的。
上面介绍next数组是在出现不匹配的情况下的回溯的位置，这个很重要，对于暴力法来说如果出现不匹配的情况我们会回溯到这次匹配的首位的下一位，对于某些情况来说会很浪费
比如主串为：aaaaaaab
待模式串为： aaab
但是如果我们通过上面的求next_0(下标从0开始)的方法先预处理好模式串的next[]：
i 0 1 2 3
str[i] a a a b
next -1 0 1 2
匹配过程如下:
i = 3, j = 3
0 1 2 3 4 5 6 7
a a a a a a a b
a a a b
|
当我们匹配到下标为3处时发生不匹配，我们查询next[j]，就可以得到下一次匹配的j的下标2
i = 3, j = 2,匹配成功 i=4, j=3匹配不成功
0 1 2 3 4 5 6 7
a a a a a a a b
a a a b
|
当我们匹配到j下标为3处时发生不匹配，我们查询next[j]，就可以得到下一次匹配的j的下标2
i = 4, j = 2匹配成功 i = 5, j = 3匹配不成功
0 1 2 3 4 5 6 7
a a a a a a a b
a a a b
|
重复以上步骤直至j等于模式串的长度就代表找到了匹配的串
next_0作next数组的完整过程代码：
public static void main(String[] args) {
// String str = "abacabab";
String str = "ababcbbcacbab";
String str2 = "bbcac";
System.out.println(KMP(str, str2));
}
//下标从0开始的next数组
static int[] getNext4(String str, int[] next4) {
next4[0] = -1;
next4[1] = 0;
for(int i = 2; i < str.length(); i++) {
int j = i - 1;
while(next4[j] != -1 && str.charAt(i-1) != str.charAt(next4[j])) j = next4[j];
next4[i] = next4[j] + 1;
}
return next4;
}
static int KMP(String str1, String str2) {
int[] next = getNext4(str2, new int[str2.length() + 1]);
int i = 0, j = 0;
while(i < str1.length() && j < str2.length()) {
if(str1.charAt(i) == str2.charAt(j)) {i++; j++;}//当[i]=[j]的时候我们匹配下一个
else if(j > 0) j = next[j];//不匹配并且j>0(防止越界)，我们令j=next[j]
else i+=1;//不满足以上两种的情况说明第一位就不匹配我们找主串的下一位
if(j == str2.length()) return i - j;//找到了返回开始下标
}
return -1;//没找到
}使用val[]作next数组的代码
public static void main(String[] args) {
// String str = "abacabab";
String str = "ababcbbcacbab";
String str2 = "bbcac";
System.out.println(KMP(str, str2));
}
//求val数组
static int[] getNext(String str, int[] next) {
next4[0] = 0;
int j = 0;
for(int i = 1; i < str.length(); i++) {
while(j > 0 && str.charAt(i) != str.charAt(j)) j = next[j-1];
if(str.charAt(i) == str.charAt(j)) next[i] = ++j;
else next[i] = j;
}
return next4;
}
static int KMP(String str1, String str2) {
int[] next = getNext(str2, new int[str2.length() + 1]);
int i = 0, j = 0;
while(i < str1.length() && j < str2.length()) {
if(str1.charAt(i) == str2.charAt(j)) {i++; j++;}//当[i]=[j]的时候我们匹配下一个
else if(j > 0) j = next[j-1];//不匹配并且j>0(防止越界)，我们令j=next[j-1]
else i+=1;//不满足以上两种的情况说明第一位就不匹配我们找主串的下一位
if(j == str2.length()) return i - j;//找到了返回开始下标
}
return -1;//没找到
}这相对于暴力法在有大量前后缀相同的情况下大大提高了效率，而由于计算机的二进制特性所有数据都是由0or1组成，这势必会产生大量的相同前后缀，所以KMP算法才会如此重要。
本文参考以下文章：(KMP-两种方法求next数组-CSDN博客)
原文地址：https://blog.csdn.net/release_lonely/article/details/142776844
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！