KMP算法
暴力解决
-
思路
从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,重新开始匹配。
我们可以这样初始化:
-
代码
public class KMP { public static int kmp(String a,String b){ char[] arr = a.toCharArray(); char[] brr = b.toCharArray(); for (int i = 0; i < arr.length; i++) { int tmp = i; for (int j = 0; j < brr.length; j++,tmp++) { if(arr[tmp] != brr[j]){ break; } } if((tmp - i) == brr.length){ return tmp - i - 1; } } return -1; } public static void main(String[] args) { String ts = "abcabde"; String ps = "abde"; System.out.println(kmp(ts,ps)); } }
优化(动态规划)
-
思路
备忘录,记录匹配串的最长前缀下标,匹配失败回退时可以退到最佳位置,减少回溯的次数
-
代码
public class KMP { public static int KMP(String ts,String ps){ char[] t = ts.toCharArray(); char[] p = ps.toCharArray(); int i = 0;//主串 int j = 0;//模式串 int[] next = getNext(ps); while (i < t.length && j < p.length){ if(j == -1 || t[i] == p[j]){ i++; j++; }else { j = next[j]; } } return j == p.length ? i - j : -1; } public static int[] getNext(String ps){ char[] p = ps.toCharArray(); int[] next = new int[p.length]; next[0] = -1; int i = 0; int k = -1; while (i < next.length - 1){ if(k == -1 || p[i] == p[k]){ next[++i] = ++k; }else { k = next[k]; } } return next; } public static void main(String[] args) { String ts = "ssssssssssb"; String ps = "abcabcmn"; System.out.println(KMP(ts,ps)); } }
-
参考文章:https://www.cnblogs.com/yjiyjige/p/3263858.html