KMP算法

KMP算法

我是也能够理解算法的意思是什么，但是其实现确实还是比较复杂的，没有办法把代码写的人人都看得懂的那种程度，那没办法 只能跟以前学图论一样，先背板子吧。

public int strStr(String haystack, String needle) {
    // 构建next数组，用于指示needle中匹配失败时应该回溯的位置
    int[] next = new int[needle.length()];
    int j = -1; // -1 代表完全没有匹配任何模版，下一个判断的索引是 0
    next[0] = j;
    
    // i 从 1 开始，因为 0 处失败必然是回到 -1
    for (int i = 1; i < needle.length(); i++) {
        // 当前字符匹配失败时，通过next数组回溯j的位置
        while (j >= 0 && needle.charAt(i) != needle.charAt(j + 1)) {
            j = next[j];
        }
        // 如果当前字符匹配成功，则更新j
        if (needle.charAt(i) == needle.charAt(j + 1)) {
            j++;
        }
        // 将当前位置的j值记录到next数组中
        next[i] = j;
    }
    
    j = -1;
    // 注意 i 从 0 开始，j 的意思是已经匹配的索引，而不是下一个判断的索引
    for (int i = 0; i < haystack.length(); i++) {
        // 当前字符匹配失败时，通过next数组回溯j的位置，j一般就会变回-1
        while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
            j = next[j];
        }
        // 如果当前字符匹配成功，则更新j
        if (haystack.charAt(i) == needle.charAt(j + 1)) {
            j++;
        }
        if (j == needle.length() - 1) {
            return i - j;
        }
    }
    // 未找到匹配的子串，返回-1
    return -1;
}

我的理解就是 j 代表的是已经匹配成功的索引，所以初始化是 -1，后面每次都是判断 j+1 的索引位置，成功才把 j 加上去。然后就是两个循环中 i 的初始值不一样，我们需要保证一个循环的终点也就是 next[0]，就像递归要有边界条件，我们在 while 中也需要一个终止条件，那就是让 j 变成 -1 。所以 next[0] 必须是 -1 。