KMP

KMP算法：看一个字符串是否包含另外一个字符串。
str1=”ABC1234de” str2=”1234”
暴力解法：str1从左往右轮着尝试每一个开头看能否匹配上str2。O(NM)
前后缀：在前缀后缀都不取到整体的情况下，长度是相等且是最长的。
abbabbk
1 2 3 4 5
k前缀：a ab abb abba abbab
k后缀: b bb abb bbab bbabb
所以k前后缀是3
前后缀是对str2求的是对较短的字符串求的，每个字符都需要这个信息。
i的前后缀如何求？ i位置看i-1和前缀后一个是否相等，相等的话，i位置前后缀就是i-1的前缀+1。
str1 i……x
str2 0……y
假设str1以i开头，看能不能配出整个str2？
i位置先和0位置比，一路相等，当来到x，y位置不相等了。
经典过程：i+1再和0位置，x回跳到i+1，y回跳0
*KMP加速过程：肯定知道y的最大前缀和最大后缀，x不变,y回跳到最大前缀之后的下一个位置。
实质：实际上是把str2推过来了,y和x接着往下配看是否相等。因为前缀和后缀是相等的，可以直接跳过加速。
还知道 i 到 j 中间都不可能配出str2，所以检查位置挪到了j，看j位置开始是否能配出str2。
i…j 中一定匹配不出str2因为假设i…j中有位置k能匹配到str2，那么k..x要和str2等量前缀一样，
那么str2会整出更长的前缀和后缀匹配，和前后缀信息数组不符合不可能，所以不成立。

    public static int getIndexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int i1 = 0;
        int i2 = 0;
        // O(M) m <= n
        int[] next = getNextArray(str2);
        // O(N)
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) { // i2 == 0   st2中没法往前跳
                i1++; // 换开头
            } else {
                i2 = next[i2]; //i2往前跳, i1可以不动
            }
        }
        // i1越界 或者 i2越界，i2越界才代表匹配到了，否则没有返回-1.
        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;// 超过长度2 人为规定 
        next[1] = 0;
        int i = 2; // 目前在哪个位置上求next数组的值
        int cn = 0; // 当前是哪个位置的值再和i-1位置的字符比较也代表当前的信息,比如7 代表和0-6是前缀，和7位置比
                    // 信息：前缀下一个的值等于前缀的长度
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) { // 配成功的时候
                next[i++] = ++cn; // 维持代码连续性：i++去求下一个位置信息，++cn=例如成功7+1=8，也代表下一个位置i，要用i-1信息,cn也要跟着+1。
            } else if (cn > 0) {// 当前跳到cn位置的字符，和i-1位置的字符匹配不上。
                cn = next[cn]; // 不相等，更新cn，往前跳,cn等于cn前缀的长度
            } else {
                next[i++] = 0;// 无法往前跳，0
            }
        }
        return next;
    }