最近在做字符串匹配,沉迷于indexof无法自拔,但是考虑到大数据处理的时间复杂度,决定研究一波KMP。
在这我就不讲什么原理了,转自: https://www.cnblogs.com/zhangtianq/p/5839909.html
String a = "BBC ABCDAB ABCDABCDABDE"; String b = "ABCDABD"; char [] alist = a.toCharArray(); char [] blist = b.toCharArray(); int [] next = new int[b.length()]; //next数组的生成 //next数组是KMP中比较难以理解的,实际就是求对应目标串的最长相同前后缀 //如ABCDAB中AB就是最长的前后缀,又如ABCDA中A就是最长的前后缀 int k = -1; int j = 0; next[0] = -1; while(j < b.length()-1){ if (k == -1 || blist[k] == blist[j]) { ++k; ++j; next[j] = k; }else { k = next[k]; } } //a,b两个字符串匹配 int i = 0; j = 0; while(i<a.length() && j<b.length()){ if (j == -1 || alist[i] == blist[j]) { i++; j++; }else{ j = next[j]; } } if (j == b.length()) { System.out.println(i-j); }else { System.out.println(-1); }