KMP算法

参考链接：
代码随想录： https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html#kmp

视频讲解版：帮你把KMP算法学个通透！（理论篇）(opens new window)
视频讲解版：帮你把KMP算法学个通透！（求next数组代码篇）(opens new window)
文字讲解版：KMP算法

求解 模式串 的 next 数组

public class KMP {
    public static void main(String[] args) {
        String start = "aabaab";

        int[] ints = countNext(start);

        for (int i = 0; i < ints.length; i++) {
            System.out.println("ints[i] = " + ints[i]);
        }
    }

    public static int[] countNext(String start) {
        int[] result = new int[start.length()];

        // i：代表对String类型的遍历
        // j：代表着最大公共前后缀的大小
        int i = 1, j = 0;
        for (; i < start.length(); i++) {
            while (j != 0 && start.charAt(j) != start.charAt(i)) {
                j = result[--j];
            }

            if (start.charAt(j) == start.charAt(i)) {
                result[i] = ++j;
            }
        }
        return result;
    }
}