首先先把这个不到九分钟的视频看一遍：

最浅显易懂的 KMP 算法讲解

无论是暴力匹配还是 KMP 算法，其实都是双指针算法。

主串指针为 i，子串指针为 j。

但是区别在于，暴力匹配的时候，主串指针会往前回退，但 KMP 匹配的时候，主串指针永远不会往前回退，因此 KMP 的效率更高。

尽管子串指针会向前回退，但是子串指针永远只跟着主串指针向后移动。因此时间复杂度为 O(n)。

其核心就是找相同的前后缀，也就是 next 数组，如果在已经匹配成功的部分中，当前的后缀有一个一模一样的前缀，那么我们下次匹配的时候，就可以直接将这个后缀当作已经匹配好的前缀来使用（看视频的动画更容易理解）。

现在问题变为：在子串中，指针指向的每一个字符作为后缀的一部分，计算出其长度最长的前缀，这个问题就是代码中 next 数组的求解，可以用动态规划解决。

完整代码

public class KMPAlgorithm {
    
    // KMP 字符串匹配算法
    public static int kmpSearch(String string, String patt) {
        int[] next = buildNext(patt); // 计算 next 数组
        
        int i = 0; // 主串指针
        int j = 0; // 子串指针
        
        while (i < string.length()) {
            if (string.charAt(i) == patt.charAt(j)) {
                // 字符匹配，指针后移
                i++;
                j++;
            } else if (j > 0) {
                // 失配，根据 next 数组回溯
                j = next[j - 1];
            } else {
                // 子串第一个字符就失配
                i++;
            }
            
            // 完全匹配
            if (j == patt.length()) {
                return i - j; // 返回匹配起始位置
            }
        }
        
        return -1; // 未匹配返回 -1
    }
    
    // 计算 next 数组
    private static int[] buildNext(String patt) {
        int[] next = new int[patt.length()];
        next[0] = 0; // 初始化第一个元素
        int prefixLen = 0; // 共同前后缀长度
        int i = 1;
        
        while (i < patt.length()) {
            if (patt.charAt(prefixLen) == patt.charAt(i)) {
                prefixLen++;
                next[i] = prefixLen;
                i++;
            } else {
                if (prefixLen == 0) {
                    next[i] = 0;
                    i++;
                } else {
                    prefixLen = next[prefixLen - 1]; // 回溯
                }
            }
        }
        
        return next;
    }

    // 测试代码
    public static void main(String[] args) {
        String string = "ababcabcacbab";
        String pattern = "abcac";
        int index = kmpSearch(string, pattern);
        System.out.println("匹配位置: " + index);
    }
}

next 数组计算

这张图是理解 next 数组计算的关键

视频位置

LeetCode 练习题

面试题 01.09. 字符串轮转