关于数据结构和算法:KMP的代码解读

48次阅读

共计 1908 个字符，预计需要花费 5 分钟才能阅读完成。

如何更好地了解和把握 KMP 算法? – 海纳的答复 – 知乎解说了 KMP 算法，清晰明了，令人醍醐灌顶。但我对其代码中不少合并与简化的局部仍须要多思考一番，这里记录下其代码思路。倡议读完下面文章后食用。

局部匹配表(Partial Match Table) PMT
PMT 中的值是字符串前缀汇合和后缀汇合的交集中最长元素的长度

假如曾经求出了 PMT。

设指针 i 指向主字符串 t，指针 j 指向模式字符串 p。
也就是说，若模式字符串 p 的 PMT[j] = k，那么模式字符串 p 的 substring(0, k) 与 substring(j - k + 1, j + 1) 是相等的。

也就是说，如果主字符串 t 与模式字符串 p 在某处不匹配了，PMT[j - 1] = k 的值示意模式字符串 p 的 substring(0, k) 曾经与主字符串 t 的 i 地位之前的 k 个地位 substring(i – k , i) 匹配过了。
因而只须要 i 不变（substring(i - k , i) 后一个），j = PMT[j - 1]（substring(0, k) 后一个）即可。

为了示意不便（PMT[j - 1] 在当 j = 0 是会数组越界，须要独自探讨），用 next 数组示意，PMT[j - 1] = next[j]，这样最初一个字符的 PMT 值就没有了，不过不必放心，j = p.length() 时，循环跳出，不须要用 PMT[p.length() - 1]。

代码如下：

public int strStr(String haystack, String needle) {
    int i = 0;
    int j = 0;
    int[] next = getNext(needle);
    while (i < haystack.length() && j < needle.length()) {if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            i ++;
            j ++;
        } else {j = next[j];
        }
    }
    return (j == needle.length()) ? (i - j) : -1;
}

当匹配时，i 与 j 都须要后退：i = i + 1; j = j + 1;
当不匹配时，i 不变，j = next[j]，j 变小，寻找更短一些的已匹配字符串持续匹配
- j >= 0，表明有 j 个字符匹配过了，从 j 地位持续匹配。若仍是不匹配，持续令 j = next[j]，，若直到 j = 0 时仍不匹配 j = next[0] = -1
- j = -1 时，阐明主字符串 t[i] 地位不会匹配了，须要持续向前走，i = i + 1；模式字符串 p 须要从头匹配，即 j = j + 1 = 0
最终，如果是模式字符串走完了（主字符串走没走完无所谓），返回 i - j 即为匹配的开始下标；否则就是没匹配完，不能匹配

注：匹配时的状况和 j = -1 的解决办法雷同，能够合并

求 next 数组的过程也齐全能够看作字符串匹配的过程，以模式字符串的后缀为 t，以模式字符串的前缀为模式字符串 p，失去 next 数组

代码如下：

public int[] getNext(String p) {int[] next = new int[p.length()];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < p.length() - 1) {if (j == -1 || p.charAt(i) == p.charAt(j)) {
            i += 1;
            j += 1;
            next[i] = j;
        } else {j = next[j];
        }
    }
    return next;
}

首先因为要用模式字符串的后缀作为 t，故 i = 1;j = 0;。先令 next[0] = -1，t 从 i = 1 开始

若匹配，阐明 p 中 substring(0, j + 1) 作为前缀时（长度 j + 1），与 t 中 substring(i - j, i + 1) 作为后缀（长度 j + 1）相等，则 i 与 j 都须要后退：i = i + 1, j = j + 1，设置下一个地位的 next [i] = j + 1（next 示意以后地位前的字符串中匹配的长度）
若不匹配，i 不变，j = next[j]（从更短的匹配的前后缀开始）
- 直到找到匹配的前后缀长度，设置 next[i]
- 若直到 j = 0 时仍不匹配 j = next[0] = -1，同样阐明 t[i] 地位不会匹配了，t 须要持续向前走，i = i + 1；p 须要从头匹配，即 j = j + 1 = 0，匹配长度为 0，设置下一个地位的值 next[i] = j = 0