主串和匹配串的字符不匹配时:得出一个规律,主串回溯 i-j+1, 匹配从头开始
主串和匹配串的字符匹配时:继续比较下一个字符,结束条件是 i 和主串长度相同或者 j 和匹配串长度相同
一般是求出匹配串在主串的开头位置
时间复杂度为O(m*n)
public class BF { public static void main(String[] args) { System.out.println(bf("wtklzh","klz")); } public static int bf(String str1, String str2){ for (int i = 0, j = 0; i < str1.length(); i++) { if(str1.charAt(i) == str2.charAt(j)){ j++; }else{ i = i-j+1; j = 0; } if(j == str2.length()){ return i - j+1; } } return -1; } }
三个外国人搞出来的,所以就以三个人名字的首字母命名的算法,时间复杂度为O(m+n)
kmp算法分为两部分:
优点:
注意:
手算匹配串:
匹配串索引: 0 1 2 3 4 5
匹配串的值: a b a b a c
getNext()的next[]数组 : 0 0 1 2 3 0 包含当前索引字符的串的重复的数量
getNext2()的next数组: 0 0 1 1 2 0 不包含当前索引字符的串的重复数量,这个算法是求废弃索引0的匹配串的数组,不然next[2] = 1解释不了
过程:看着代码走一遍流程,索引0没有废弃 默认索引0处的值为0,也就是a对应的next[0] = 0 b的子串是a,j这时为0, next[1] = 0; a往前找,这时j = 0, i = 2,这个时候arr[i] == arr[j] 都是a,j++,j这时是1,next[2] = 1 b往前找,这时j = 1, i = 3,j>0 但是 arr[3] == arr[1],都是b, j++ 这时j是2,next[3] = 2 a往前找,这时j = 2, i = 4, j>0 但是arr[4] == arr[2],都是a, j++,这事j是3,next[4] = 3 c往前找,这时j = 3, i = 5, j>0 arr[5] != arr[3]、c!=b,将j = next[j-1]=next[2]=1,这时j是2 j>0, arr[5] != arr[2]、c!=a,将j = next[j-1] = next[1] = 0, 这时j是1 j>0, arr[5] != arr[0]、c!=a,将j = next[j-1] = next[0] = 0,这时j是0 j>0不成立,arr[5] != arr[0],将next[i] = j、next[5] = 0
原理:
匹配串索引: 0 1 2 3 4 5
匹配串的值: a b a b a c
getNext()的next[]数组 : 0 0 1 2 3 0 包含当前索引字符的串的重复的数量
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3jHOh9Og-1641023247340)(C:\Users\18225\AppData\Roaming\Typora\typora-user-images\image-20220101154149073.png)]
参考:
https://www.bilibili.com/video/BV1uJ411s7br/?spm_id_from=autoNext
代码
import java.util.Arrays; public class KMP { public static int[] getNext(String arr){ //初始化一个数组,长度是匹配串的长度 int[] next = new int[arr.length()]; next[0] = 0; for (int i = 1,j = 0; i < arr.length(); i++) { while (j>0 && arr.charAt(i) != arr.charAt(j)){ j = next[j - 1]; } if(arr.charAt(i) == arr.charAt(j)){ j++; } next[i] = j; } System.out.println(Arrays.toString(next)); return next; } //这个算法是求废弃索引0的匹配串的数组,不然next[2] = 1解释不了 public static int[] getNext2(String arr){ //初始化一个数组,长度是匹配串的长度 int[] next = new int[arr.length()]; next[0] = 0; next[1] = 0; int i = 1, j = 0; while(i < arr.length()-1){ if(j == 0 || arr.charAt(i) == arr.charAt(j)){ next[++i] = ++j; }else { j = next[j]; } } System.out.println(Arrays.toString(next)); return next; } public static int kmp(String str1, String str2){ //获得匹配数组的next数组 int[] next = getNext(str2); //循环主串,kmp的主串不用回溯 for (int i = 0, j = 0; i < str1.length(); i++) { //不匹配 while (j > 0 && str1.charAt(i) != str2.charAt(j)){ //kmp中,匹配串不在回到头部,根据next数组记录的值,来决定匹配串的位置 j = next[j-1]; } //匹配 if(str1.charAt(i) == str2.charAt(j)){ j++; } //匹配串匹配完成结束程序 if(j == str2.length()){ return i-j+1; } } return -1; } public static void main(String[] args) { System.out.println(kmp("wtklzh","klz")); System.out.println(kmp("aaaabc","aababac")); } }