[KMP]串匹配-java代码

串匹配算法大家都不陌生，其中kmp算法算是比较经典的一种算法，然而kmp算法的精髓就是寻找next[ ]数组。

主要是对匹配串的next[ ]一个求解。

[java]
package qyq.Algorithm.KMP;
/**
* KMP串匹配
* @author qi
* @creation 2012-8-14
*/
public class Kmp {

public static void main(String[] args) {
String S="abcdthabc";
String T="bcdmmn";
int lenS=S.length();
int lenT=T.length();
int next[]=new int[lenT+1];

getNext(T, next);//next[]数组的求解
for(int i=0;i System.err.println(next[i]);
}
int kmp=K_next(S, T, lenS, lenT, next);
System.err.println("第一次匹配的位置::"+kmp);
}

public static void getNext(String T,int next[]){
int j=1,k=0;
next[1]=0;
while(j if(k==0||T.charAt(j)==T.charAt(k)){
j++;
k++;
next[j]=k;
}else {
k=next[k];
}
}
}

public static int K_next(String S,String T,int lenS,int lenT,int next[]){
int i=0,j=0;
while(i if(j==0||S.charAt(i)==T.charAt(j)){
i++;
j++;
}else {
j=next[j];
}
}
if(j==lenT){
return i-lenT;
}
return -1;
}
}