```
package DataStructure;
public class KMP {
public int indexOf(String source, String pattern) {
int i = 0, j = 0;
char[] src = source.toCharArray();
char[] ptn = pattern.toCharArray();
int sLen = src.length;
int pLen = ptn.length;
int[] next = getNext(ptn);
while (i < sLen && j < pLen) {
// 如果j = -1,或者當前字符匹配成功(src[i] = ptn[j]),都讓i++,j++
if (j == -1 || src[i] == ptn[j]) {
i++;
j++;
} else {
// 如果j!=-1且當前字符匹配失敗,則令i不變,j=next[j],即讓pattern模式串右移j-next[j]個單位
j = next[j];
}
}
if(j == pLen) {
return i - j;
}
return -1;
}
public int[] getNext(char[] p) {
// 已知next[j] = k,利用遞歸的思想求出next[j+1]的值
// 如果已知next[j] = k,如何求出next[j+1]呢?具體算法如下:
// 1. 如果p[j] = p[k], 則next[j+1] = next[k] + 1;
// 2. 如果p[j] != p[k], 則令k=next[k],如果此時p[j]==p[k],則next[j+1]=k+1,
// 如果不相等,則繼續遞歸前綴索引,令 k=next[k],繼續判斷,直至k=-1(即k=next[0])或者p[j]=p[k]為止
int pLen = p.length;
int[] next = new int[pLen];
int k = -1;
int j = 0;
next[0] = -1; // next數組中第一位next[0]為-1
while (j < pLen - 1) {
if (k == -1 || p[j] == p[k]) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
public static void main(String[] args){
KMP kmp = new KMP();
String a = "ababc";
String b = "ababababcababc";
int[] next = kmp.getNext(a.toCharArray());
for(int i = 0; i < next.length; i++){
System.out.println(a.charAt(i)+" "+next[i]);
}
int res = kmp.indexOf(b, a);
System.out.println(res);
}
}
```
