KMP算法

实在愚笨，一直没看懂KMP算法。
在大神的指点下，终于弄懂了next数组的求解。

• next[i]的含义是在ms[i]之前的字符串ma[0..i-1]中，必须以ms[i-1]结尾的后缀子串与必须以ms[0]开头的前缀子串最大匹配长度是多少。
• 当ss[j]!=ms[j-i]时，在ss中要匹配的位置仍是j不进行回退；而ms向又滑动，让ms[k]滑动到与str[j]同一个位置上，继续后续的匹配检查。

参考资料：
严蔚敏的数据结构&大神的指点

public static int getIndexOf(String s ,String m){
        if (s == null || m == null || m.length() > s.length() || m.length() < 1) {
            return 0;
        }
        char[] ss = s.toCharArray();
        char[] ms= m.toCharArray();
        int si =0;
        int mi =0;
        int[] next = getNextArray(ms);
        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi] || mi == 0) {  //当ss与ms匹配或mi为0
                si++;
                mi++;
            } else {   //ss不动，ms滑动
                mi = next[mi];
            }
        }
        return mi == ms.length ? si - mi : 0;
    }

    public static int[] getNextArray(char[] ms) {
        /**
         * 当Pk=Pj，next[j+1]=next[j]+1
         * 当Pk!=Pj，next[j+1]=next[k]+1
         */
        int i=1,j=0;
        int[] next = new int[ms.length+1];   //next[0]没有作用
        next[1]=0;
        while (i<ms.length){
            if (j == 0 || ms[i] == ms[j]) {  
                ++i;++j;
                next[i]=j;
            }else {
                j=next[j];
            }
        }
        return next;

下面是一个求next数组的例子：
match：abaabcac
next[j]：01122312