KMP算法
title: KMP算法 id: 2b62eca118d9c07131c0c8e23dc5b31d tags: [] date: 2000/01/01 00:00:00 updated: 2023/03/04 19:29:12 isPublic: true --#|[分隔]|#--
KMP算法
适用场景
给定一个长字符串，再给定短字符串，判断这个长字符串是否包含短字符串。
当短字符串自己内部有小循环时，性能优化程度更大(比如ababc、abcab等等)。
暴力解的方式
暴力解的话，时间复杂度为O(mn)，m和n分别为长字符串和短字符串的字符数。
但实际上，短字符串本身，可能会局部重复自身，比如：
长字符串：
abababc短字符串：
ababc
可以发现，按照暴力解法，会遍历长字符串，依次从每个字符开始，对比后面几位是否和段字符串完全一致。
let result = judge('abababc', 'ababc')
console.log(result)
// 判断方法
function judge(longStr, shortStr) {
// 双层遍历, 一次对比
for (let i = 0; i < longStr.length; i++) {
for (let j = 0; j < shortStr.length; j++) {
// 判断是否匹配相等
if (longStr[i + j] === shortStr[j]) { // 相等,进一步判断
if (j === shortStr.length - 1) { // 是否是 shortStr 的最后一个字符,也就是全相等了
return true
} else continue
} else break // 不相等, 跳出当前循环
}
}
return false
}可以发现，两个字符串的前4个字符是全等的，但第5个字符不等，按照逻辑，内部for循环跳出，外部for循环的i加1，再开始依次对比，所以时间复杂度是O(mn)
KMP算法的具体思路
解析整理短字符串
先处理短字符串，找出其内部的小循环，比如ababc中，两个ab就形成了循环。
声明一个数组table，长度为短字符串的长度，然后遍历短字符串，给table对应位置设置上数字：
概括说明：table中，索引值为index的数字number，表示的是，短字符串的索引为index的字符，预计和它本身的索引值为number的那个字母是重复的。
详细举例说明：
table的索引值为0的一项的值为0：短字符串索引值为0的字母为a，预计和索引值为0的字母a相同table的索引值为1的一项的值为0：短字符串索引值为1的字母为b，预计和索引值为0的字母a相同table的索引值为2的一项的值为0：短字符串索引值为2的字母为a，预计和索引值为0的字母a相同table的索引值为3的一项的值为1：短字符串索引值为3的字母为b，预计和索引值为1的字母b相同table的索引值为4的一项的值为2：短字符串索引值为4的字母为c，预计和索引值为2的字母a相同
遍历长字符串对比时，对算法进行调整
之前遍历长字符串对比的思路是：从长字符串的每一项开始，往后依次和短字符串进行全等比较(可查看上面的暴力解的代码示例)
现在的思路需要调整：
长字符串从
i = 0开始，短字符串从j = 0开始，结束条件是长字符串被遍历完依次对比
长字符串[i]和短字符串[j]如果相等，就
++i和++j，循环再次判断，直到把短字符串遍历完，则说明有全重复的了，可以记录下来i的值，再把j = 0，再继续循环如果不相等，则判断
j是否等于0若
j === 0，则++i，继续循环若
j !== 0，则设置j = table[j]（关键），并继续循环
这里整体完成后，能拿到若干个开始重复的索引值，这样的索引值有几个，就说明有几个循环。
这里对上面的关键进行说明，不一定能明白，最好是打开代码，用脑编译，跟着流程一步步走一走：
当 j === 0，说明当前对比就是短字符串的第 1 个字符，第一个字符就不一样，那就可以 ++i，继续下一次循环了
当 j !== 0，说明当前对比的是短字符串中间的某个字符，而短字符串有可能是内部循环的，是否循环我们已经有记录了，就在 table 中，table[j] 就是记录当前这个字符，和前面的索引值为几的字符是重复的。
虽然是预计重复，但不一定真重复，所以 j = table[j] 后，i 的值不变就再去循环判断
只要 table[j] !== 0，就说明当前字符，是处在一个短字符串的内部循环中的。
既然 j 能走到这个值，说明短字符串的前面几位，和长字符串最近几位是全等的，那说明长字符串的这部分，也是和短字符串一样是内部循环的。
如下所示，长字符串和短字符串的前 4 位相同，但第 5 位的红字 a 和 c 不相同(github不支持行内样式，看不到颜色)：
长字符串：abababc
短字符串：ababc
table的值为：[0, 0, 0, 1, 2]
此时 i === j === 4 ，设置 j = table[j]，则 j === table[4] === 2，在按照逻辑去循环(此时 i === 4, j === 2)，对比变成了如下所示：
长字符串：abababc
短字符串：ababc
也就是舍弃了长字符串的前两位，从第3为开始对比，短字符串则认为只对比到了第 3 位。
长字符串的第 5 位，和短字符串的第 3 位的红色的字符都为 a，预计的相等真的相等了，可以把 a 标绿。
就这样，长字符串从第三位开始、短字符串从第一位开始，继续对比了。
当然，如果此时红字处的双方仍然不等，按照上面的逻辑，需要设置 j = table[j]，也就是 j === table[2] === 0，相当于把 j 归零了，也就是重头开始对比短字符串，逻辑也是正确的。
代码实现
Last updated
Was this helpful?