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

如何更好地了解和把握 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

啰啰嗦嗦说完了，总结一下就是：
利用 next 数组记录前缀后缀雷同的最长字符串，用来在匹配字符串过程中，当匹配失败时，一直在模板字符串中寻找主字符串指针之前曾经实现匹配的子字符串，再次尝试从主字符串指针地位持续匹配，缩小主字符串反复遍历的工夫

心愿过段时间还能看懂这写的是啥吧~~

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

匹配过程

求 PMT/ next 数组

总结