java实现的KMP算法
public class KMPAlgorithm {?
?
???/**
????* 计算模式串的next函数
????*?
????* @param desStr
????*??????????? 模式串
????* @return 模式串的next函数，用数组来保存
????*/?
???private static int[] kmpNext(String desStr) {?
???????int len = desStr.length();?
???????int i = 0;?
???????int j = -1;?
???????int next[] = new int[len];?
???????while (i < len - 1) {?
???????????if (j == -1 || (desStr.charAt(i) == (desStr.charAt(j)))) {?
??????????????? i++;?
??????????????? j++;?
??????????????? if (desStr.charAt(i) !=(desStr.charAt(j))) {?
??????????????????? next[i] = (j + 1);?
??????????????? } else {?
??????????????????? next[i] = next[j];?
??????????????? }?
???????????} else {?
??????????????? j = (next[j] - 1);?
???????????}?
???????}?
???????return next;?
?
???}?
?
???/**
????* kmp的核心算法
????*?
????* @param sourceStr
????* @param desStr
????* @param pos
????*??????????? 从主串的第几个字符开始匹配
????* @return 成功的话返回位置，失败的话返回-1，索引从0开始的
????*/?
???public static int index(String sourceStr, String desStr, int pos) {?
???????int next[] = kmpNext(desStr);?
???????int i = 0;?
???????int j = 0;?
???????while (i < sourceStr.length() - 1 && j < desStr.length() -1) {?
???????????if (j == 0 || (sourceStr.charAt(i) == desStr.charAt(j))) {?
??????????????? i++;?
??????????????? j++;?
???????????} else?
??????????????? j = (next[j] - 1);?
???????}?
???????if (j > desStr.length() - 2) {?
???????????return (i - desStr.length() + 1);?
??? ????} else?
???????????return -1;?
?
???}?
?
}??
