最近学到基础课的 KMP 算法，一开始给整懵逼了，后来看了阮一峰的博客懂了，代码的话 LeetCode 官方题解写的挺好，可以将那个代码当作模板背一下

阮一峰的博客：字符串匹配的KMP算法-阮一峰的网络日志

知乎上的一个回答： https://www.zhihu.com/question/21923021/answer/281346746

KMP 模板
出自 LeetCode 官方题解

// haystack 是字符串，needle 是模板串
public int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m == 0) {
        return 0;
    }
    // 构建 pi 数组
    int[] pi = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
            j = pi[j - 1];
        }
        if (needle.charAt(i) == needle.charAt(j)) {
            j++;
        }
        pi[i] = j;
    }
    // 匹配过程
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
            j = pi[j - 1];
        }
        if (haystack.charAt(i) == needle.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。