KMP 算法
目录
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] 位置
原文地址：https://blog.csdn.net/2301_76161469/article/details/142885185
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！