KMP算法

这里暂时只是记录一下KMP算法代码，详细步骤以后有时间再整理

public class Main{

    public static int[] getNext(String str){
        char p[] = str.toCharArray();
        int next[] = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j<p.length-1){
            if(k==-1 || p[j]==p[k]){
                if(p[++j]==p[++k]){    //这里是一个优化
                    next[j] = next[k];
                }else{
                    next[j] = k;
                }
            }else{
                k = next[k];
            }
        }
        return next;
    }
    public static int KMP(String str,String pattern){
        char s[] = str.toCharArray();
        char p[] = pattern.toCharArray();
        int i=0,j=0;
        int next[] = getNext(pattern);
        while(i<s.length && j<p.length){
            if(j==-1 || s[i]==p[j]){
                ++i;
                ++j;
            }else{
                j = next[j];
            }
        }
        if(j==p.length){
            return i-j;
        }else{
            return -1;
        }

    }
    public static void main(String[] args)  {
        String str = "AHUAHUFUFGFYGEWYFEWFEWUFUEWFHUHFSDHFJDSHFI";
        String pattern = "ABCDABCDBCD";
        System.out.println("Index  "  +  KMP(str,pattern));
    }
}