目录

KMP 算法

算法思路

为什么不需要在主串中进行回退

计算 next 数组

代码实现

next 数组优化

 查找所有起始位置

---

KMP 算法

KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为 克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

在文章 BF 算法-CSDN博客 中我们学习了 BF 算法，在使用 BF 算法查找主串中的子串时，当主串中的字符和子串中的字符匹配失败时，需要在主串和子串中进行回退

​

而 KMP 是改进的字符串匹配算法，不需要在主串中进行回退，只需要在子串中进行回退

接下来，我们就来学习如何在子串中进行回退，也就是 KMP 的算法思路

算法思路

为什么不需要在主串中进行回退

我们通过一个例子来看：

​

定义 i 指向主串的 0 下标，j 指向子串的 0 下标，接着，以主串 0 下标位置为起始位置开始匹配

可以看到，主串中的 "abcab" 与 子串中的 "abcab" 都相同

而当 i = 5，j = 5 时，主串中的字符与子串中的字符不相同

​

在 BF 算法中，我们会将 i 回退到 i - j + 1 位置，j 回退到 0 下标位置

这是因为以 0 下标为起始位置匹配失败，但是以 1 下标位置可能会匹配成功，此时，需要将 i 回退到 原起始位置 + 1 的 新起始位置

由于要开始新一轮的匹配，因此 j 也需要回退到 0 下标位置

在上述例子中，若我们将 i 回退到 1 下标位置，j 回退到 0 下位置，第一个字符就会匹配失败

​

当 i 回退到 2 位置 也会在第一个字符就匹配失败

​

而当 i 回退到 3 下标位置 时，第一个字符匹配成功，后续也有可能会匹配成功：

​ 

当 i 回退到 4 下标位置 时， 也会在第一个字符就匹配失败

​

在上述例子中，当 i 进行回退时，会有大量一定不会匹配成功的起始位置存在，在判断这些一定会匹配失败的起始位置时，就会浪费很多时间

而 KMP 算法则不会将 i 进行回退，而是只将 j 回退到合适的位置

不将 i 进行回退，不会漏掉可能会匹配成功的起始位置吗？

这个问题我们先不直接解决，而是继续通过例子进一步理解

我们继续看上面的例子，在 i 回退到 3 下标位置时：

​

进行匹配： 

​ 

ab 匹配成功，继续判断 e 和 c，我们可以发现：以 3 为起始位置开始的新一轮匹配，回到了 原来匹配失败的位置

​

 此时，我们就可以不将 i 进行回退，而是只用将 j 回退到 2 下标位置

​

为什么可以直接将 j 回退到 2 位置呢？

当 i = 5，j = 5 时，说明子串中的前 5 个字符一定与主串匹配成功

而在这前五个字符中，我们可以看到子串中的前两个字符 ab 和 最后两个字符 ab 相同

因此，主串中的最后两个字符 ab 也就一定能与 子串中前两个字符 ab 匹配成功：

 因此，我们就不用将 i 回退到 3 下标位置，将 j 回退到 0 下标位置，因为此时 主串 的前两个字符一定会和 子串 前两个字符匹配成功，i 会再次回到未回退时的位置，j 会回到 2 下标位置

当不回退 i，只将 j 回退到合适位置时，就会省去判断大量一定不会匹配成功的起始位置的时间

再看上一个问题： 不将 i 进行回退，不会漏掉可能会匹配成功的起始位置吗？

在上述例子中，只有将 i 回退到 3 下标位置时才可能会匹配成功，此时的 i 是可能会匹配成功的起始位置，而 i 回退到 3 时，一定会再次回到 未回退时的下标位置

而 i 会回到这个下标的前提是

在未进行回退时，j 下标前的所有字符中：

在 最前面（以 0 为起始位置的字符串）和 最后面（以 j 为结束位置的字符串）有相同的连续字符的情况下

此时，i 回退到 3 位置时，就一定会和前两个字符匹配成功，也就一定会回到未回退时的位置

也就是说，当 j 位置之前字符串中 存在 最前面（以 0 为起始位置的字符串）和 最后面（以 j - 1 为结束位置的字符串）有 相同 L 个连续字符 时，将 i 回退到 i - L 位置（新的起始位置）时，新的起始位置中前 L 个字符一定与子串中前 L 个字符相同，i 也就一定会回退到 未回退时的位置（原 i 位置）

此时，就无需再将 i 进行回退，而是只用将 j 回退到合适位置，就可以确定新的可能会匹配成功的起始位置

因此，不将 i 进行回退，不会漏掉可能会匹配成功的起始位置（要彻底证明不将 i 进行回退，不会漏掉可能会匹配成功的起始位置，需要利用数学相关知识进行严格的证明，在这里就不进行说明了） 

计算 next 数组

接着，我们要解决下一个问题，当匹配失败时，如何确定 j 回退的位置呢？

 我们需要有一个 next 数组，来存放子串中每个位置回退的对应位置

接着，就需要计算每个位置回退的位置

当 j 位置之前字符串中 存在 最前面（以 0 为起始位置的字符串）和 最后面（以 j - 1 为结束位置的字符串）有 相同 L 个连续字符 时，新的可能会匹配成功的起始位置中的前 L 个字符一定会与子串中的前 L 个字符匹配成功，此时，就可以继续判断主串中 i 位置字符和子串中 L 位置字符是否相同，因此，j 需要回退到 L 位置

此时，问题就转换成了：

找到 j 位置之前字符串中 最前面（以 0 为起始位置的字符串）和 最后面（以 j - 1 为结束位置的字符串） 相同的连续字符，也就是在匹配成功部分找两个相同的字符串，一个以 0 下标开始，一个以 j - 1 下标结束

我们通过一个例子来看：

当 j 为 0 时，j 位置之前没有元素，也就不存在 最前面（以 0 为起始位置的字符串）和 最后面（以 j - 1 为结束位置的字符串） 相同的连续字符，因此，我们让其回退到 -1 位置，next[0] = -1

当 j 为 1 时，j 位置之前只有一个元素， 当其匹配失败时，一定会回到 0 下标位置重写开始匹配，因此，next[1] = 0

无论任何数据，在 next 数组中，next[0] = -1，next[1] = 0

关于为什么 next[0]  = -1 我们后续再进行详细解释  

我们先继续向后分析

当 j 为 2 时，j 位置之前有两个元素，但是，不存在以 a 开头，以 b 结尾的两个相同字符串，因此，也只能回退到 0 位置重新开始匹配

当 j 为 3 时，j 位置之前有三个元素，但是，不存在以 a 开头，以 c 结尾的两个相同字符串，因此，也只能回退到 0 位置重新开始匹配

当 j 为 4 时，j 位置之前有四个元素，此时，存在以 a 开头，以 a 结尾的相同字符串 "a"，因此，此时可以不用回退到 0 位置，而是回退到 1 位置

当 j 为 5 时，j 位置之前有五个元素，此时，存在以 a 开头，以 b 结尾的两个相同字符串 "ab"，因此，此时可以不用回退到 0 位置，而是回退到 2 位置

当 j 为 6 时，j 位置之前有六个元素，此时，存在以 a 开头，以 c 结尾的两个相同字符串 "abc"，因此，此时可以不用回退到 0 位置，而是回退到 3位置

当 j 为 7 时，j 位置之前有七个元素，但是，其中不存在以 a 开头，以 d 结尾的两个相同字符串，因此需要回退到 0 位置重新开始匹配

也就是说：

在 j 位置之前（匹配成功部分）：

若存在两个相同的长度为 L 的字符串（一个以 0 位置开始，一个以 j - 1位置结束）时，j 回退的下标为 L

若不存在，则 j 回退的下标为 0

那么，我们如何编写代码来寻找这两个相同的字符串呢？

还是通过上述例子来看，

当 j 为 4 时，匹配成功部分存在以 a 开头，以 a 结尾的相同字符串 "a"

当 j 为 5 时，匹配成功部分存在以 a 开头，以 b 结尾的相同字符串 "ab"

当 j 为 6 时，匹配成功部分存在以 a 开头，以 c 结尾的相同字符串 "abc"

我们可以发现：

设存在两相同的字符串，以 0 位置开头的字符串为 str1，以 j - 1 位置结束的字符串为 str2，两字符串长度为 L（若不存在，则 str1 = str2 = ""，L = 0）

在 j = 4，且 str1 和 str2 都为 "a" 的前提下，str1 和 str2 后面一个字符相同，则 j = 5 时，str1 与 str2 也相同，都为 "ab"，此时 j 回退到 2 下标位置

在 j = 5，且 str1 和 str2 都为 "ab" 的前提下，str1 和 str2 后面一个字符相同，则 j = 6 时，str1 与 str2 也相同，都为 "abc"，此时 j 回退到 3 下标

即，由于 str1 与 str2 相同，而若 str1 后面的一个字符，和 str2 后面一个字符相同，则新的两个字符串也一定相同

也就是说：

在 j 下标位置，若匹配失败，回退的位置为 L ，而若 str1 和 str2 后面一个字符都相同，则 j + 1 下标匹配失败时，回退的位置为 L + 1，因此，我们可以根据 j 回退的下标位置，求出 j + 1 将要回退的下标

 j 要回退的下标为 L，即 next[j] = L，若在子串 target 中，j 位置字符等于 L 位置字符（target.charAt(j) = target.charAt(L)），则 next[j + 1] = L + 1

那么，如果 target.charAt(j) != target.charAt(L) 时，next[j + 1] 的值为多少呢？

例如： 

 ​​​​​

当 j = 5 时，  target.charAt(j) != target.charAt(L) ，此时 j + 1该回退到哪里呢？

此时 j + 1 下标之前，str1 = str2 = "a"，则 L = 1，next[j] = 1

在 j = 5 时，j 回退到 L（2 下标）位置时，  target.charAt(j) != target.charAt(L) ，不匹配，此时，在 L （2）位置的基础上继续回退，即 L = next[next[j]] = next[L]

next[L] = 0，此时就回退到了 0 下标位置

而此时 ，0 下标位置的 a 与 j 下标位置的 a 相同，匹配成功，next[j + 1] = L + 1 = 0 + 1 = 1

因此，若 target.charAt(j) != target.charAt(L)，则继续回退，一直回退（L = next[L]），直到 target.charAt(j) = target.charAt(L)

若一直不存在 target.charAt(j) != target.charAt(L) 的情况呢？ 

 此时就会最终回退到 -1 位置（也就是 next[0]），此时，也就是说，j + 1 位置之前，不存在两个相同的字符串（一个以 0 位置开始，一个以 j 位置结束），此时，j 就需要回退到 0 下标位置

由于 L = -1，此时的 next[j + 1] 也为 L + 1（-1 + 1 = 0）

这也就是前面遗留的问题：为什么 next[0] = -1?

可以通过 -1 判断出 j + 1 位置之前，不存在以 0 位置开始 和以 j 位置结束的两个字符串，且由于 next[0] = -1，next[j + 1] 也可以通过 L + 1 来进行计算，即 target.charAt(j) = target.charAt(k) 或 k = -1时，next[j + 1] = L + 1

最后，我们来总结一下上述求 next 数组的过程

（1）无论任何数据，其 next[0] = -1，next[1] = 0

（2）定义 j 为当前位置，k（也就是 L）为 j 需要回退的位置（next[j]）

（3）从 1 位置开始，依次向后求 next[j + 1]

（3）判断  target.charAt(j) 是否等于 target.charAt(k)，

                若相等或是 k = -1，则 next[j + 1] = k + 1；

                若不相等，则继续回退（k = next[k]）

分析清楚之后，我们就来编写代码解决问题

代码实现

    /*** 判断主串中是否含有子串* @param str 主串* @param target 子串* @return 若主串中含有子串，返回主串中子串第一次出现的起始下标；若不含有，返回 -1*/public int KMP(String str, String target) {// 处理特殊情况if (str == null || target == null) {return -1;}int strLen = str.length();int targetLen = target.length();if (strLen == 0 || targetLen > strLen) {return -1;}// 求 next 数组int[] next = new int[targetLen];getNext(next, target);// 开始判断int i = 0, j = 0;while (i < strLen && j < targetLen) {// 判断 str 中 i 位置字符是否与 target 中j 位置字符相同// 不要忘记处理 j = -1 的情况if (j == -1 || str.charAt(i) == target.charAt(j)) {// 相同，i 和 j 都向后移动i++;j++;} else {// 不相同，j 进行回退j = next[j];}}// 子串先遍历完if (j >= targetLen) {return i - j;} else {// 主串先遍历完return -1;}}/*** 求 j 位置匹配失败时，应该回退的下标位置* @param next 存放 j 应该回退的位置* @param target 子串*/private void getNext(int[] next, String target) {// 处理特殊情况if (target == null) {return;}int len = next.length;if (len == 0) {return;}next[0] = -1;// 若子串中只有一个字符，直接返回if (len == 1) {return;}next[1] = 0;int j = 1, k = 0;// 遍历子串，依次求 j + 1 位置的回退下标while (j < len - 1) {// 当 k 为 -1 或 j 位置字符与 k 位置字符相同时，next[j + 1] = k + 1// 不要忘记处理 k = -1 的情况if (k == -1 || target.charAt(j) == target.charAt(k)) {// 更新 j 和 k 的值j++;k++;next[j] = k;} else {// 继续回退k = next[k];}}}

在匹配过程中，不要忘记处理 j = -1 的情况

当 j = -1 时，说明子串中的第一个字符就与主串中 i 位置的字符匹配失败了，此时 j 为 0 ，回退到了 -1 位置
由于 i 与 j 第一个字符匹配失败了，因此 i 需要向后移动，继续判断，j = -1，也需要进行自增，回到 0 下标位置，继续与与主串中的字符进行匹配

next 数组优化

在上述过程中，当主串中的 i 位置与子串中的 j 位置字符匹配失败时，需要将 j 进行回退

有时 j 需要回退很多次

  

那么，能否 "一步到位"，直接找到最终要回退的位置呢？

接下来，我们就来对 next 数组进行优化，优化后的数组，我们用 nextval 来表示

我们通过一个具体的例子来看如何计算 nextval

当 j = 0 时，j 最终会退回到 -1 位置，因此，nextval[0] = -1 

而当 j = 1 时，若此时匹配失败（也就是 j 位置的字符 a 与主串中 i 位置的字符匹配失败），需要进行回退

next[1] = 0，因此回退到 k =  0 下标位置

但此时 0 下标位置的字符 a 与 1 下标的字符 a 相同，因此，k 位置的字符 a 与主串中 i 位置的字符一定会匹配失败，因此还需要继续回退到 next[k]，也就是 -1 位置

因此，nextval[1] = -1

继续看 j = 2 时， 若此时匹配失败（字符 a 与主串中 i 位置的字符匹配失败），需要进行回退，next[2] = 1，回退到 k = 1 下标位置

由于此时 1 下标位置的字符 a 与 2 下标的字符 a 相同，此时仍然会与主串中 i 位置字符匹配失败，因此还需要继续回退，而 nextval[1] = -1，也就是说 1 下标位置匹配失败时，最终会回到 -1 位置，因此，j = 2 位置匹配失败时，最终也会回到 -1 位置

通过上述示例，我们可以发现：

在 j 下标位置匹配失败时，会回退到 k 位置（也就是 next[j] 位置），而 若 k 位置的字符与 j 位置的字符相同 时，此时 k 位置字符也一定会与主串中 i 位置字符匹配失败，进而继续回退，而 k 位置最终会回退到 nextval[k] 位置，因此，j 下标也会最终回到 nextval[k] 位置

 也就是说，当 k 位置字符与 j 位置字符相同 时，j 位置最终会回退到 nextval[k] 位置，即 nextval[j] = nextval[k]

若 k 位置字符与 j 位置字符不相同呢？

我们接着看上述例子：

当 j = 3 时，若此时匹配失败（也就是 主串中 i 位置字符不为 b），会回退到 k =  2 下标位置

但是，由于 k 位置字符与 j 位置字符不相同，因此，我们无法确认主串中 i 位置字符与 k 位置字符是否相同，也就无法确认能否继续进行回退，因此，j 最终回退的位置为 k 位置，也就是 next[j]

总结一下：

若回退的 k 位置与当前 j 位置字符相同，此时还会继续回退，nextval[j] = nextval[k]

若回退的 k 位置与当前 j 位置字符不相同，不能再继续回退，nextval[j] = k

我们总结一下 nextval 数组的计算过程

（1）无论任何数据，其 nextval[0] = -1

（2）定义 j 为当前位置，k 为 j 需要回退的最终位置（nextval[j]）

（3）从 0 位置开始，依次向后求 nextval[j + 1]

（3）判断  target.charAt(j) 是否等于 target.charAt(k)，

                若相等或是 k = -1，判断 j + 1 位置的元素与 k + 1 位置元素是否相同，若相同，则直接回退到 nextval[k+1] 位置；若不相同，则回退到 k + 1 位置

                若不相等，进行回退（k = nextval[k]）

接下来，我们就在代码中实现 nextval 数组的计算：

    private void getNextval(int[] nextval, String target) {// 处理特殊情况if (target == null) {return;}int len = nextval.length;// 若没有元素，则直接返回if (len == 0) {return;}nextval[0] = -1;// 初始化 j 和 k 的值int j = 0, k = -1;// 遍历子串，依次求 j + 1 位置的回退下标while (j < len - 1) {if (k == -1 || target.charAt(j) == target.charAt(k)) {// 更新 j 和 k 的值j++;k++;// 将 j 回退到最终位置nextval[j] = target.charAt(j) != target.charAt(k) ? k : nextval[k];} else {// 继续回退k = nextval[k];}}}

上述我们查找的是主串中子串第一次出现时的起始位置，那么， 若我们想要查找主串中与子串相同的字符串的所有起始位置，该如何实现呢？

 查找所有起始位置

与查找 主串中子串第一次出现的起始位置 思路相同

但是，当我们找到第一个起始位置（也就是 j 第一次遍历完子串时）时

不能直接返回，而是应该存储起始位置（i - j），然后继续查找下一个起始位置

在这时就需要对 j 进行回退

由于此时的 j 已经越界，那么，j 该回退到哪里呢？

我们来看一个例子： 

当 j = 2 时，k = 1

而当 j = 3 时，在 j 之前，存在以 a 开头，以 a 结尾的字符串"aa"

 也就是说，我们依然可以利用之前的方式来求越界时 j 应该回退的下标位置

设子串长度为 len，当 j 位于子串最后一个位置（len - 1）时：

若 target.charAt(len - 1) = target.charAt(k)，则 next[len] = k + 1

 而若  target.charAt(len) != target.charAt(k)时，则进行回退

最终也能计算出 next[len] 的值，也就是 len 回退的位置

因此，我们可以直接在原来计算 next 数组的基础上多计算一位，也就是 len 位置应该回退的位置（next[len]）

对于上述计算，我们可以这样进行理解：

我们可以将子串看做是 长度为 len + 1 的字符串

但是 len 位置的字符非常特殊，它不会和任何字符匹配成功，也就意味着这个位置必然会匹配失败，也就必然会进行回退

这样，由于 len 位置无论如何都不会匹配成功，也就是子串最多只能匹配到 len - 1 位置，当 j = len 时，就意味着已经匹配成功，此时保存起始位置，再进行回退，就很容易求出所有子串的起始位置

代码实现：

由于在 getNext 方法中，我们是通过 next 数组的长度来判断计算多少个回退位置的

因此，我们只需要传递长度为 len + 1 的数组就可以计算出 0 - len 对应的回退位置了

    /*** 查找所有起始位置* @param str 主串* @param target 子串* @return 查询结果集*/public List<Integer> findAll(String str, String target) {List<Integer> ret = new ArrayList<>();// 处理特殊情况if (str == null || target == null) {return ret;}int strLen = str.length();int targetLen = target.length();if (strLen == 0 || targetLen > strLen) {return ret;}// 求 next 数组(计算 targetLen + 1 位)int[] next = new int[targetLen + 1];getNext(next, target);// 开始判断int i = 0, j = 0;while (i < strLen) {// 判断 str 中 i 位置字符是否与 target 中 j 位置字符相同// 不要忘记处理 j = -1 的情况if (j == -1 || str.charAt(i) == target.charAt(j)) {// 相同，i 和 j 都向后移动i++;j++;// 判断是否已经匹配成功if (j == targetLen) {ret.add(i - j);j = next[j];}} else {j = next[j];}}return ret;}

在查找所有起始位置时，也可以使用 nextval 数组

由于 len 位置无论如何都不会匹配成功，也不会与 k 位置字符相同，此时就只能回退到 k 位置

也就是说：

当 j 位于 len 位置，或 j 位置字符不等于 k 位置字符时，j 回退到 k 位置

当 j 位置字符等于 k 位置字符时，j 回退到 nextval[k] 位置