Java实现kmp算法

public class KMP {
private int[] next;

public int[] getNext(String pattern) {
int length = pattern.length();
int[] next = new int[length];
next[0] = -1;

int i = 0;
int j = -1;
while (i < length - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}

return next;
}

public int kmp(String str, String pattern) {
int[] next = getNext(pattern);

int i = 0;
int j = 0;
int sLength = str.length();
int pLength = pattern.length();
while (i < sLength && j < pLength) {
if (j == -1 || str.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}

if (j == pLength) {
return i - j;
} else {
return -1;
}
}
}