KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速的匹配的目的.具体实现是通过一个next() 函数来实现的，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
KMP 和 BF 唯一不一样的地方在，主串的i并不会回退，并且 j 也不会移动到 0 号位置
举例：
引出 next 数组
KMP的精髓就是 next 数组：也就是用 next[ j ]=k 来表示，不同的 j 来对应一个K值，这个K就是你将来要移动的 j要移动的位置。
而K 的值是这样求得：
1. 找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标0开始，另一个以 j -1下标结尾。
2. 不管什么数据 next [ 0 ] =-1;next[ 1 ]=0；k就等于真子串的长度。
求 next数组的练习：
练习1：举例对于“ababcabcdabcde",求其的 next 数组
-1 0 0 1 2 0 1 2 0 0 1 2 0 0
练习2：再对”abcabcabcabcdabcde", 求其的 next 数组
-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
代码实现:
/** * Created with IntelliJ IDEA. * Description: * User: zhao3 * Date: 2023-08-18 * Time: 13:38 */ public class Main { /** * 创建next 数组 * @param: next * @param: sub * @return: void * @Author: zsl **/ public static void getNext(int[] next,String sub){ int len=sub.length(); if(len==0){ return; } if(len>0){ next[0]=-1; } if(len>1){ next[1]=0; } int k=0; int i=2; while(i<sub.length()) { if (k == -1 || sub.charAt(k) == sub.charAt(i - 1)) { next[i] = k + 1; k++; i++; } else { k = next[k]; } } } /** * @param: str 主串 * @param: sub 子串 * @param: pos 主串匹配的起始位置 * @return: void * @Author: zsl **/ public static int KMP(String str,String sub,int pos){ int i=pos; int j=0; int lens= str.length(); int lensub=sub.length(); int[] next=new int[sub.length()]; getNext(next,sub); while (i<lens&&j<lensub){ if(j==-1||str.charAt(i)==sub.charAt(j)){ i++; j++; }else { j=next[j]; } } if(j==lensub) return i-j; return 0; } public static void main(String[] args) { System.out.println(KMP("abcabcdefabc", "bcf", 0)); } }
next 数组优化
对aaaaaaaaaab next数组为[-1,0,1,2,3,4,5,6,7,8,0]
当我们在主串与子串匹配时
while (i<lens&&j<lensub){ if(j==-1||str.charAt(i)==sub.charAt(j)){ i++; j++; }else { j=next[j]; } }
当子串的下标为9,且与主串不匹配时,就会回退,但此时我们会发现,由于j每次回退的位置对应的字符与初始时的字符相同,大大增加了时间复杂度,因此我们可以将其优化为nextval 数组,当我们在创建nextval 数组时:
while(i<sub.length()) { if (k == -1 || sub.charAt(k) == sub.charAt(i - 1)) { next[i] = k + 1; k++; i++; }else { k = next[k]; } }
当 k回退后,再次匹配 sub.charAt(k) == sub.charAt(i - 1)成功后,我们需要再次判定 next[i]==next[k+1]? 如果相等,就继续回退,直到 next[i]!=next[k+1]或k==-1.
nextval 的实现:
while(i<sub.length()) { if (k == -1 || sub.charAt(k) == sub.charAt(i - 1)) { next[i] = k + 1; k++; i++; } else { while (sub.charAt(k)!=sub.charAt(i-1)||sub.charAt(i)==sub.charAt(k+1)) { k = next[k]; if(k==-1){ break; } } } }
