KMP 算法

public static int strStr(String text, String pattern) {
    int textLen = text.length();
    int patternLen = pattern.length();
    for (int i = 0; i < textLen - patternLen; i++) {
        boolean flag = true;
        for (int j = 0; j < patternLen; j++) {
            if (pattern.charAt(j) != text.charAt(i + j)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return i;
        }
    }
    return -1;
}

"a" 无意义，不满足前后缀定义，i 从 1 开始
"aa"     i = 1, j = 1, next[1] = 1
"aab"    i = 2, j = 0, next[2] = 0
"aaba"   i = 3, j = 1, next[3] = 1
"aabaa"  i = 4, j = 2, next[4] = 2
"aabaaf" i = 5, j = 0, next[5] = 0

int patternLen = pattern.length();
    int[] next = new int[patternLen];
//    构造next[]
//    i 指向 子串的最后
//    j 指向 前缀的最后
    for (int i = 1, j = 0; i < patternLen; i++) {
//        不匹配, j 为 长度-1 子串的结果
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
//        长度为 i 的子串的最长公共前后缀的长度为 j, 索引为 j - 1
//        即存放公共前后缀之后的字符的索引
        next[i] = j;
    }

int textLen = text.length();
//    search
//    i 指向 text
//    j 指向 pattern
    for (int i = 0, j = 0; i < textLen; i++) {
//        不匹配, j 为 长度-1 子串的结果,
//        直到匹配, 边界情况为 j = 0
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
//        匹配, j 后移
//        除前面全不匹配外，均匹配
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == patternLen) {
            return i - patternLen + 1;
        }
    }

public static int kmp(String text, String pattern) {
        int textLen = text.length();
        int patternLen = pattern.length();
        int[] next = new int[patternLen];
//        构造next[]
//        i 指向 子串的最后
//        j 指向 前缀的最后
        for (int i = 1, j = 0; i < patternLen; i++) {
//            不匹配, j 为 长度-1 子串的结果
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
//            长度为 i 的子串的最长公共前后缀的长度为 j, 索引为 j - 1
//            即存放公共前后缀之后的字符的索引
            next[i] = j;
        }
//        search
//        i 指向 text
//        j 指向 pattern
        for (int i = 0, j = 0; i < textLen; i++) {
//            不匹配, j 为 长度-1 子串的结果,
//            直到匹配, 边界情况为 j = 0
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
//            匹配, j 后移
//            除前面全不匹配外，均匹配
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == patternLen) {
                return i - patternLen + 1;
            }
        }
        return -1;
    }