学习自：http://www.cnblogs.com/SYCstudio/p/7194315.html
我的实现
public final static List<Integer> KMP(String a, String b) {
List<Integer> res = new ArrayList<>();
int[] next = new int[b.length()];
next[0] = -1;
for(int i = 1; i < next.length; ++i) {
int j = next[i-1];
while(b.charAt(i) != b.charAt(j + 1) && j >= 0)
j = next[j];
if(b.charAt(i) == b.charAt(j + 1)) {
next[i] = j + 1;
}
else {
next[i] = -1;
}
}
int i = 0;
int j = 0;
while(i < a.length()) {
if(a.charAt(i) == b.charAt(j)) {
i++;
j++;
if(j == b.length() - 1) {
res.add(i - b.length() + 1);
j = next[j - 1] + 1;
}
}
else {
if(j == 0)
i++;
else
j = next[j - 1] + 1;
}
}
return res;
}
