对于查找字符子串在父字符串中出现的位置，我们可以使用KMP算法。
KMP算法的实现原理是使子串向右滑尽可能的远，这就涉及到求滑动距离的数组next[].
next[]数组中每个元素求解的公式是{ k|max(str.suString(0,k) == str.subString(i-k+1,i)) }；
private static void KMPNext(int[] next, String str){
for(int i=0;i<str.length(); i++){
for(int j=1; j< i; j++){
String first = str.substring(0, j);
String second = str.substring(i-j+1, i+1);
System.out.println("i="+i +" j="+j+" first:"+first + " second:"+second);
if(first.equals(second)){
if(j > next[i]){
next[i]=j;
System.out.println(" next["+i+"]="+next[i]);
}
}
}
}
}
这里需要附加说明的是str.substring(start, end)函数，其截取的字符串是从第start个字符开始到第end个字符结束，但不包括第end个字符。注意是不包括第end个字符。
求取next数组中还有一点点小窍门，可以减少一点的计算量。
下面对上述方法进行修改。
由于从下表0开始有点不方便思考（太笨了），所有下标都从1开始。
求next数组，其实可以利用next已经得出的信息求的，方法原理如下：（来自hihoCoder）
实现代码如下：
private static void KMPNext1(int[] next, String son){
son = new String(" "+son);
next[0] = -1;
next[1] = 0;
int p=1, q=next[1];
while( p < (son.length() - 1)){
if(son.charAt(p+1) == son.charAt(q+1)){
p++;
q++;
next[p] = q;
}else{
q = next[q];
}
if( q == -1){
p++;
q++;
}
}
}
使用上述KMPNext1方法求出的结果是：如bababb->{-1,0,0,1,2,3,1}，next[i]=-1表示匹配失败。
利用上述得到的next数组，便可以对父串和子串进行比较了，见如下代码：
private static int KMP(String father, String son){
int times = 0;
int[] next = new int[son.length() + 1];
KMPNext1(next, son);
next[0] = -1;
father = new String(" "+father);
son = new String(" "+son);
int p=0, q=0;
while( p< (father.length() - 1) ){
if(father.charAt(p+1) == son.charAt(q+1)){
p++;
q++;
if(q>=(son.length() - 1)){
times++;
q=next[q];
}
}else{
q = next[q];
}
if(q == -1){
p++;
q++;
}
}
return times;
}