JZTXT

KMP算法 代码

发布时间 2023-09-04 16:27:58作者: 郑择徽
public class KMP算法 {
    public static void main(String[] args) {
        String str1="BBCABCDABABCDABCDABDE";
        String str2="ABCDABD";
        int[]next=getNext(str2);
        System.out.println(Arrays.toString(next));
        int res=kmpSearch(str1,str2,next);
        System.out.println(res);
    }


    private static int kmpSearch(String str1,String str2,int[]next){
        int j=0;
        for(int i=0;i<str1.length();i++){
            while(j>0 && str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if(j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }


    private static int[] getNext(String str){
        int[]next=new int[str.length()];
        next[0]=0;
        int j=0;
        for(int i=1;i<next.length;i++){
            while(j>0 && str.charAt(i)!=str.charAt(j)){
                j=next[j-1];
            }
            if(str.charAt(i)==str.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}