KMP

KMP 算法解决的问题：
字符串 str1 和 str2，str1 是否 包含 str2，如果包含返回 str2 在 str1 中的位置。

暴力遍历的方法：
匹配每个 str1 的字符串，在极端情况下复杂度极高，如 str1 = “111111112”，str2=”112”。复杂度几乎为 （N、M 分别为 str1、str2 的长度）

前置知识：
k 为字符串前后缀相同的最大长度。
如：对于字符串 abbabb， k = 3

对于字符串 aaaaa 来说，k = 4

str2 的每个下标对应的 k：k 之前的字符串最大

在传统的遍历过程中，如果 str1 出现在匹配第 i 位置是否和 str2 不同，接着就会再比较 i=i+1 位置

但是，str2 在已经知道了每个下标的 k，就可以直接这样匹配

即，str1 在 i 位置和 str2 做匹配，如果在 str1 的 x 位置 和 str2 的 y 位置 不匹配，那么就可以使 y = k[y] i = x-k[y]，然后继续匹配

能够这样匹配 KMP 算法保证了两个条件：

1. str2 每个位置上的 k 都保证了该位置下标之前的前后缀相同的最大长度，也就是说：在 k > 0 时， str2[0] ~ str2[k[i]] （abef）和 str2[k[i-k[i]]] ~ str2[k[i-1]] （abef）相同

1. 在 [i, x-k[y]] （abefzq） 范围匹配不到 str2

如下图 str2 黄色的部分是在 y 位置的前后缀的最大长度。 str2 和 str1 的 i 位置匹配并在 str1 的 x 位置 str2 的 y 位置匹配不上，str2 在 str1 [i, j] 范围内匹配不到

证明过程：
假设在 [i, j] 范围上存在 m 位置 str2 能匹配到的字符串
所以，在 str1 上一定存在 [m, x-1] 范围上的字符串一定能和 str2 的 [0, x-m] 相同。如下图的绿色部分

也就是说，str2 上的[m , y-1] 的字符串和 [0, x-m] 相同，如下绿色部分

即，str2 中绿色的部分是相同的，改推论和“str2 最大的前后缀是黄色的部分”的结论相悖，所以在 [i, j] 上不存在和 str2 匹配的字符串。

public class KMP {
    static int findIndexOf(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0 || str1.length() < str2.length()) {
            return -1;
        }
        char[] str1Arr = str1.toCharArray();
        char[] str2Arr = str2.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] kArr = getKArray(str2Arr);
        while (i1 < str1Arr.length && i2 < str2Arr.length) {
            if (str1Arr[i1] == str2Arr[i2]) {
                i1++;
                i2++;
            } else if (kArr[i2] == -1) {
                i1++;
            } else {
                i2 = kArr[i2];
            }
        }
        // i1 或者 i2 越界了
        return i2 == str2Arr.length ? i1 - i2 : -1;
    }
    // 获取每个位置的最大前后缀
    private static int[] getKArray(char[] chars) {
        if (chars.length == 1) return new int[]{-1};
        int[] kArr = new int[chars.length];
        kArr[0] = -1;
        kArr[1] = 0;
        // 当前的下标
        int i = 2;
        // 统计最大的前后缀
        int count = 0;
        while (i < kArr.length) {
            if (chars[i - 1] == chars[count]) {
                kArr[i++] = ++count;
            } else if (count > 0) {
                // 取上一个位置的 k
                count = kArr[count];
            } else {
                kArr[i++] = 0;
            }
        }
        return kArr;
    }
    public static void main(String[] args) {
        String str1 = "abbaefzqabbabbefdqe";
        String str2 = "abbabb";
        System.out.println(str1);
        System.out.println(str2);
        System.out.println(findIndexOf(str1, str2));
    }
}

结果

abbaefzqabbabbefdqe
abbabb
8