KMP 子字符串匹配算法学习笔记

二、长度为前 2 个字符的子串aa，最长相同前后缀的长度为 1。

三、长度为前 3 个字符的子串aab，最长相同前后缀的长度为 0。

以此类推：

四、长度为前 4 个字符的子串aaba，最长相同前后缀的长度为 1。

五、长度为前 5 个字符的子串aabaa，最长相同前后缀的长度为 2。

六、长度为前 6 个字符的子串aabaaf，最长相同前后缀的长度为 0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

可以看出前缀表里的数值代表着就是：当前位置之前的子串有多大长度相同的前缀后缀。

再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要看前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是 2， 所有把下表移动到下表 2 的位置继续比配。可以再反复看一下上面的动画。

最后就在文本串中找到了和模式串匹配的子串了。

[](()前缀表有什么问题

来看一下刚刚求的这个前缀表有什么问题呢？


看这个位置红框的位置，如果要找下表 1 所对应 前缀表里的数值的时候，前缀表里的数值依然是 1，然后就要跳到下表 1 的位置，如此就形成了一个死循环。

**如何怎么避免呢，就把前缀表里的数值统一减一， 开始位置设置为-1 **。 这一点对理解后面 KMP 代码很重要！！

改为如图所示：

这样就避免的死循环，只不过后续取 前缀表里的数值的时候，要记得再+1，才是我们想要的值。

最后得到的新前缀表在 KMP 算法里通常用一个 next 数组来表示。

注意这个 next 数组就根据模式串求取的。

[](()使用 next 数组来匹配

有了 next 数组，就可以根据 next 数组来 匹配文本串 s，和模式串 t 了。

注意 next 数组是新前缀表（旧前缀表统一减一了）。

匹配过程动画如下：

[](()放码过来

下文统称 haystack 为文本串, needle 为模式串。

[haystack, needle 出处](()。

[](()构造 next 数组

定义一个方法 getNext 来构建 next 数组，参数为一个名为 next 数组，和一个字符串。代码如下：

private void getNext(int[] next, String s) {}

构造 next 数组其实就是计算模式串 s，前缀表的过程。主要有如下三步：

1. 初始化

2. 处理前后缀不相同的情况

3. 处理前后缀相同的情况

[](()一、初始化

定义两个指针 i 和 j：

• j 指向前缀终止位置（严格来说是终止位置减一的位置），

• i 指向后缀终止位置（与 j 同理）。

（通常是先 i 后 j，为什么这里相反，接下来看代码就清楚了。）

然后还要对 next 数组进行初始化赋值，如下：

int j = -1;

next[0] = j;

• j 初始化为 -1 原因是前文说过前缀表要统一减一的操作（避免死循环得情况），所以 j 初始化为-1。

• next[] 表示 i（包括 i）之前最长相等的前后缀长度（其实就是 j），next[0]初始化为 j 。

[](()二、处理前后缀不相同的情况

因为 j 初始化为-1，那么 i 就从 1 开始，进行 s[i] 与 s[j+1]的比较。（这里可能一开始不适应理解，不用急。）

所以遍历模式串 s 的循环下表 i 要从 1 开始，代码如下：

for(int i = 1; i < s.length(); i++) { // 注意 i 从 1 开始

如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要回退。

如何回退？next[j]就是记录着 j（包括 j）之前的子串的相同前后缀的长度。

那么 s[i] 与 s[j+1] 不相同，就要找 j+1 前一个元素在 next 数组里的值（就是 next[j]）。

所以，处理前后缀不相同的情况代码如下：

while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 前后缀不相同了

j = next[j]; // 回退

}

[](()三、处理前后缀相同的情况

如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给 next[i], 因为 next[i]要记录相同前后缀的长度。

代码如下：

if (s.charAt(i) == s.charAt(j + 1)) { // 找到相同的前后缀

j++;

}

next[i] = j; // 将 j（前缀的长度）赋给 next[i]

最后整体构建 next 数组的函数代码如下：

private void getNext(int[] next, String s) {

int j = -1;

next[0] = j;

for(int i = 1; i < s.length(); i++) { // 注意 i 从 1 开始

while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 前后缀不相同了

j = next[j]; // 向前回溯

}

if (s.charAt(i) == s.charAt(j + 1)) { // 找到相同的前后缀

j++;

}

next[i] = j; // 将 j（前缀的长度）赋给 next[i]

}

}

代码构造 next 数组的逻辑流程动画如下：

得到了 next 数组之后，就开始用它做匹配。

[](()使用 next 数组来做匹配

在文本串 haystack 里找是否出现过模式串 needle。定义两个下表 j 指向模式串起始位置，i 指向文本串其实位置。

那么 j 初始值依然为-1，这是因为 next 数组里记录的起始位置为-1。

i 就从 0 开始，遍历文本串，代码如下：

for (int i = 0; i < haystack.length(); i++) { // 注意 i 就从 0 开始

接下来就是 haystack.charAt(i) 与 needle.charAt(j + 1) （因为 j 从-1 开始的） 进行比较。

如果 haystack.charAt(i) 与 needle.charAt(j + 1) 不相同，j 就要从 next 数组里寻找下一个匹配的位置。

代码如下：

while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { // 不匹配

j = next[j]; // j 寻找之前匹配的位置

}

如果 haystack.charAt(i) 与 needle.charAt(j + 1) 相同，那么 i 和 j 同时向后移动， 代码如下：

if (haystack.charAt(i) == needle.charAt(j + 1)) { // 匹配，j 和 i 同时向后移动

j++;

}

如果 j 指向了模式串 t 的末尾，那么就说明模式串 t 完全匹配文本串 s 里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置（从 0 开始），所以返回当前在文本串匹配模式串的位置 i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。

代码如下：

if (j == (needle.length() - 1) ) { // 文本串 s 里出现了模式串 t

return (i - needle.length() + 1);

}

[](()代码总览