[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<next.length;i++){//打印出next数组 
            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<T.length()){ 
            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<lenS&&j<lenT){ 
            if(j==0||S.charAt(i)==T.charAt(j)){ 
                i++; 
                j++; 
            }else { 
                j=next[j]; 
            }    
        } 
        if(j==lenT){ 
            return i-lenT; 
        } 
        return -1; 
    } 
} 

补充：软件开发 , Java ,

上一个：服务提供者框架
下一个：J2SE基础夯实系列之使用StackTraceElement封装，打印调试代码！