KMP

kmp.jpg

kmp算法最主要的是计算出next数组
[0,0,1,2,0,1,2,3,1]
len:表示next[i]处的值
next数组主要是如果新加入的字符和pattern[len]不相同是该怎么算len=next[len-1] 回退到next[len-1] 对应字符的next的值

public class KMP {
    public static int kmp(String str, String dest,int[] next){//str文本串  dest 模式串
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return 0;
    }
    public static int[] kmpnext(String pattern){
        char patterns[]=pattern.toCharArray();
        int[] next = new int[pattern.length()];
        next[0] = 0;
        int len=0;
        int i=1;
        while (i<next.length) {
            if (patterns[i]==patterns[len]) {
                len++;
                next[i]=len;
                i++;
            }else{
                if (len>0) {
                    len=next[len-1];
                }else{
                    next[i]=0;
                    i++;
                }
            }
        }
        return next;
    }
    public static void main(String[] args){
        String a = "ababa";
        String b = "ssdfgasdbababa";
        int[] next = kmpnext(a);
        for(int i = 0; i < next.length; i++){
            System.out.print(next[i] +" ");            
        }
       int res = kmp(b, a,next);
        System.out.println(res);
        
        System.out.println(next.length);
    }
}