kmp_matching.java

kmp算法实现

package kmp_algorith;

public class KMP_Matching {
    private int[] next;
    // computes the next[j]
    void setNext(String p){
        char P[]=new char[p.length()];
        P=p.toCharArray();
        next=new int[p.length()];
        int j=0;
        int k=-1;
        next[0]=-1;
        while(j<p.length()-1){
        if(k==-1||P[j]==P[k]){
            j++;
            k++;
            if(P[j]==P[k])next[j]=next[k];
            else
            next[j]=k;             
        }
        else{
            k=next[k];
        }
        }
    }
    // do the matching operator
    int kmp_Algorithm(String t,String p,int k){
        setNext(p);
        char[] T=t.toCharArray();
        char[] P=p.toCharArray();
        if(k<0||k>t.length()){
            return -1;
        }
        int i=k;
        int j=0;
        while(i<t.length()&&j<p.length()){
            if(j==-1||T[i]==P[j]){
                i++;
                j++;
            }
            else{
                j=next[j];
            }
        }
        return((j==p.length())?i-p.length():-1);
    }
    public static void main(String arg[]){
        String t="abcabcaabcabcabbacb";
        String p="abcabcabbac";
        int result;        
        KMP_Matching obj1=new KMP_Matching();
        result=obj1.kmp_Algorithm(t,p,0);
        System.out.println("the values of the next array");
        for(int i=0;i<p.length();i++){            
            System.out.print(obj1.next[i]+" ");
        }
        System.out.println();
        if(result==-1){
            System.out.println("Not Match");
        }
        else{
            System.out.println("Match in "+result);            
        }
        
    }
     
}