/**
* KMP算法用来处理字符串匹配问题
* 原理介绍:找到匹配失败时的最合适的回退位置，而不是简单的回退到子串的第一个字符(常规的枚举查找方式，是简单的回退到子串的第一个字符),即可提高查找的效率.
* 因此为了找到这个合适的位置,先对子串预处理,从而得到一个回退位置的数组.
*
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置，此过程是子串的自我匹配过程，类似于KMP过程
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到子串第i个字符匹配失败时，子串的一个回退位置
for(int i=1;i<size;i++){
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}
/**
* KMP实现
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当子串的第j个字符(B[j])不等于源串的第i个字符(A[i])时，对B字符串进行回退，回退到A[i-j+ 1..i]与B[1..j]相等
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//当子串的第j个字符(B[j])匹配源串的第i个字符(A[i])时，j加1
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}
public static void main(String[] args) {
kmp("abcdeg, abcdeh, abcdef","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit","ititit");
}
}
