1.KMP算法

有两个字符串str1和str2，问你在str1中是否有str2，如果有，返回str2在str1中开始的下标位置。
str1 = ”abbaabbbabaa”
str2 = ”abbaaba”
KMP算法引入了一个next数组，next[i]表示的是前i的字符组成的这个子串最长的相同前缀后缀的长度！
例如字符串aaba b aaba的相同前缀后缀有a和aaba，那么其中最长的就是aaba。
首先算出str2的next数组。
举个例子：
str1 = ”abaabaabbabaaabaabbabaab”
str2 = ”abaabbabaab”
next[] = -1 0 0 1 1 2 0 1 2 3 4
发现i = j = 5时，str1[5] != str2[5],则找到next[j] = 2，说明str2[5]之前的最大相同前缀后缀的长度为2，直接将str2的长度为2的前缀匹配到str1的长度为2的后缀上，再依次比较。直至全部找到str2
图片说明 

public class KMP {

    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2);
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) {
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == str2.length ? i1 - i2 : -1;
    }

    public static int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) {
                cn ++;
                next[i ++] = cn;
            } else if (cn > 0) {    //              i
                cn = next[cn];      //abab c abab a k
            } else {
                next[i ++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));

    }
}