/**
* @author JaJing
*/
public class KMP {

    public static void main(String[] args){
        String t = "sssabaabssabababaaaas";
        String p = "abababaaa";
        System.out.println(find(t, p));
    }


    public static int find(String text, String pattern){
        if(text == null || text.length() == 0 || pattern == null || pattern.length() == 0) return -1;
        int n = text.length();
        int m = pattern.length();
        int i=0,j=0;
        int[] next = getNext(pattern);
        while(i < n && j < m){
            if(text.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
                if(j == m){
                    return i-j;
                }
            }else{
                j = next[j];
                if(j == -1){
                    j++;
                    i++;
                }
            }
        }
        return -1;
    }

   //这是计算移动数的一种经典方式
    public static int[] getNext(String pattern) {

        char[] p = pattern.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]) {

                next[++j] = ++k;

            } else {

                k = next[k];

            }

        }

        return next;

    }
}

//这是计算对称数的一种方式，到最后本质都一样
public static int[] getNext2(String pattern){
        //匹配串总长度
        int m = pattern.length();
        //匹配串从第1个字符到第i个字符这端字符串 所包含的相同前后缀最大长度，也就是第i个字符的len记录为next[i]，比如abab，因为abab的最大前后缀是ab，len=2,next[4]=len=2
        int len = 0;
        int[] next = new int[m+1];//构造长度为m+1是为了避免最后往后挪动一位next数组，
        next[0] = -1; //特殊位置，表示text
        next[1] = 0;//一个字符没有前后缀
        for(int i=1;i<m;){
            //匹配，在上一个len的基础上+1
            if(pattern.charAt(i) == pattern.charAt(len)){
                next[i+1] = ++len;//如果采用挪动的算法，这里就是next[i] = ++len;
                i++;
            }
            //未匹配，回退
            else if(len > 0){
                len = next[len];//如果采用挪动的算法，这里就是len = next[len-1]
            }
            //未匹配，并且此时len = 0不能再回退，就把len赋予0,并继续下一个i的计算
            else{
                next[i+1] = 0;//如果采用挪动的算法，这里就是next[i] = 0;
                len = 0;
                i++;
            }
        }
        //next[m] 用不上
        System.out.println(Arrays.toString(next));
        return next;
    }