kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间,使匹配的复杂度降为O(n+m)。
朴素匹配：
/**
* 朴素模式匹配
*
* @param source 目标串
* @param pattern 模式串
*/
private static void plain(String source, String pattern) {
int res=0;
int sourceLength=source.length();
int patternLength=pattern.length();
for(int i=0;i<=(sourceLength-patternLength);i++){
res++;
String str=source.substring(i, i+patternLength);
if(str.equals(pattern)){
System.out.println("朴素模式：匹配成功");
break;
}
}
System.out.println("朴素模式：一共匹配" + res + "次数");
}
public static void main(String[] args){
String str = "ababababababb";
String dest = "abababb";
plain(str, dest);
}
KMP 算法匹配
/**
* 朴素模式匹配
*
* @param source 目标串
* @param pattern 模式串
*/
public class KMP {
public static int kmp(String source, String pattern,int[] next){//str文本串 dest 模式串
for(int i = 0, j = 0; i < source.length(); i++){
while(j > 0 && source.charAt(i) != pattern.charAt(j)){
j = next[j - 1];
}
if(source.charAt(i) == pattern.charAt(j)){
j++;
}
if(j == pattern.length()){
return i-j+1;
}
}
return 0;
}
public static int[] kmpnext(String pattern){
int[] next = new int[pattern.length()];
next[0] = 0;
for(int i = 1,j = 0; i < pattern.length(); i++){
while(j > 0 && pattern.charAt(j) != pattern.charAt(i)){
j = next[j - 1];
}
if(pattern.charAt(i) == pattern.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
public static void main(String[] args){
String a = "ababa";
String b = "ssdfgasdbababa";
int[] next = kmpnext(a);
int res = kmp(b, a,next);
System.out.println(res);
for(int i = 0; i < next.length; i++){
System.out.println(next[i]);
}
System.out.println(next.length);
}
}
参考：