KMP
算法确实不太容易理解,即使我能用PPT模拟出来指针的操作,但对其中核心的 Next
数组的代码实现还是有些困惑。
我再详细学习一下Next数组的实现再补充该文章。抱歉!
如果对 KMP
中的核心 Next
数组实现有兴趣,可以参考这些优质课程:
数据结构与算法基础--第06周05--第4章串、数组和广义表5-4.3串的操作--串的匹配算法2--KMP算法
懒猫老师-数据结构-(15)KMP算法2-next数组(模式匹配,字符串匹配)
KMP字符串匹配算法2
package KMP;
import java.util.Arrays;
public class KMPAlgorithm {
public static void main(String[] args) {
String str = "BBC ABCDAB ABCDABDDABDE";
String subString = "ABCDABD";
int[] next = getNext(subString);
System.out.println("next = " + Arrays.toString(next));
int index = Index_KMP(str, subString, next);
System.out.println("索引值为: " + index);
}
/**
* KMP搜索算法
*
* @param str1 要查找的主串
* @param str2 子串
* @param next 部分匹配表
* @return 如果是-1,则没有匹配到,否则返回到第一个匹配的位置
*/
public static int Index_KMP(String str1, String str2, int[] next) {
// 初始化指针位置
int i = 0;
int j = 0;
// 开始循环比较
while (i < str1.length() && j < str2.length()) {
if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
++i;
++j;
// 继续比较后序字符
} else {
j = next[j]; // 模式串向后移动
}
}
if (j >= str2.length()) { // 因为下标是从0开始的
return i - str2.length();
} else {
return -1; // 未找到
}
}
/**
* 获取字符串的部分匹配值
*
* @param dest
* @return
*/
public static int[] getNext(String dest) {
// 创建一个Next数组,保存部分匹配值
int i = 0; // 前指针
int j = -1;// 后指针
// 创建next数组保存部分匹配值
int[] next = new int[dest.length()];
next[0] = -1;
while (i < dest.length() - 1) {
if (j == -1 || dest.charAt(j) == dest.charAt(i)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
}