KMP算法——数据结构与算法学习
KMP算法
算法的背景
KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
核心思想
KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。
算法图解：
当算法移动到上述位置时：（发生不匹配）
发现公共前后缀为A，于是移动公共前后缀到下面位置：
为什么能够保证移动时就不会出现再匹配的情况呢
因为这里可以采用反证的手段，如果在移动时出现匹配，则就说明公共前后缀与所确定的模式串的公共前后缀不同，这就产生矛盾了。
KMP算法的思考
核心代码
求next数组（这里next数组表示模式串的公共前后缀个数）
//获取字符串的部分匹配值表
public static int[] kmpNext(String dest){
int[] next = new int[dest.length()];
next[0] = 0;
for (int i = 1, j = 0; i < dest.length(); i++) {//j可以代表匹配时的一个计算变量
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}else{
j = next[j - 1];//如果出现匹配不成功则直接赋值0
}
next[i] = j;//找到i对应的j值，比如第一个字母A就是1，AB就是2
}
return next;
}
求KMP算法：
public static int kmpSearch(String str1,String str2,int[] next){
for (int i = 0,j = 0; i < str1.length(); i++) {//这里使用两个指针进行匹配
while(j > 0 && str1.charAt(i) != str2.charAt(j)){
j = next[j - 1];//这里是核心中的核心
}
if(str1.charAt(i) == str2.charAt(j)){
j++;//指针前移
}
if(j == str2.length()){
return i - j + 1;//这加个1是因为考虑到索引问题
}
}
return -1;
}
链接：https://www.dianjilingqu.com/617758.html
