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对应位置设置上数字：

// ababc
// 00012
let table = [0, 0, 0, 1, 2]

概括说明：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 归零了，也就是重头开始对比短字符串，逻辑也是正确的。

代码实现

/**
 * KMP算法
 * 传入长和短字符串, 返回长字符串包含短字符串的起始索引值
 * 不包含则返回 -1
 * @param {String} longStr 
 * @param {String} shortStr 
 */
function KMP(longStr, shortStr) {
  let shortStrLength = shortStr.length
  let table = new Array(shortStrLength).fill(0)

  { // 处理边界
    // 没有传入长或短字符串
    if (!longStr) {
      if (shortStr) return -1
      return 0
    }
    if (!shortStr) return 0
    if (longStr.length < shortStr.length) return -1
  }
  // 生成table
  {
    let i = 1; j = 0
    while(i < shortStrLength - 1) {
      if (shortStr[i] === shortStr[j]) {
        ++j
        ++i
        table[i] = j
      } else {
        if (j > 0) {
          j = table[j]
        } else {
          ++i
        }
      }
    }
  }

  // 查找
  {
    let i = 0; j = 0, indexArr = []
    while(i < longStr.length) {
      if (longStr[i] === shortStr[j]) { // 字符相等
        if (j === shortStrLength - 1) { // 发现是短字符串最后一位, 包含了
          return i - j // 减一下,才是长字符中包含的短字符串的起始索引
        }
        ++j
        ++i
      } else { // 字符不相等
        if (j > 0) {
          j = table[j]
        } else {
          ++i
        }
      }
    }
    // 不包含
    return -1
  }
}

console.log(KMP("hello", "ll")) // 2
console.log(KMP("aaaaa", "bba")) // -1
console.log(KMP("a", "a")) // 0
console.log(KMP("", "a")) // -1