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;?

?

???}?

?

}??