My Muri Life

切换主题

本页目录

匹配问题篇 ​

抛出问题 ==> 对于给定任意字符串s1 = 'abcabaskjljlhcggd'与目标串s2 = 'jljlh'：

  • 若s2是s1的子串，那么我们需要求出s2在s1中的起始下标位置；
  • 若不是则返回-1。

KMP算法 ​

什么是KMP算法？

首先我们能想到的做法就是在s1，s2中逐位比较的暴力搜索。而KMP算法就是在暴力搜索的基础上利用next数组进行加速！

next数组又是什么呢？

现在我们声明一个next数组，该数组的每项有：

  • next[i]表示目标串s2中i位置前（不含该位置）能够匹配（即相同）的最长前缀与最长后缀的匹配长度（不能取到整体）。 比如s2 = 'jljlh'中位置i === 4处（i从0开始）的字符h有：
    • 当前/后缀长度为1时：前缀为pre = 'j'，后缀为suf = 'l'，不能匹配（即不相同），此时next[4] = 0；
    • 当前/后缀长度为2时：前缀为pre = 'jl'，后缀为suf = 'jl'，能匹配，此时更新next[4] = 2；
    • 当前/后缀长度为3时：前缀为pre = 'jlj'，后缀为suf = 'ljl'，不能匹配，此时依然next[4] = 2；
    • 由于不能取该位置（i === 4）前的子串整体即'jljl'，所以next[4]的最长前后缀匹配长度为2。
  • 特别地，根据上述定义next[0] = 0，next[1] = 0，故初始化next数组时可将全部元素初始化为0。

算法过程描述：

对给定的任意串s1与s2分别声明i、j指针，从头遍历串，当i指针未越界时：

  • 若两指针处所指字符相同，则将指针步增，考察下一字符；
  • 若不同：
    • 当j > 0时，将j指针赋值为next[j]的值，即j指针前跳至前一个前后缀匹配的最大长度处（加速操作）；
    • 当j === 0时，步增i指针。

当i或j越界时：

  • 若i越界，这说明s2不是s1的子串；
  • 若j越界，这说明s2是s1的子串，起始下标即i-j。

如何求next数组？

对于next数组，当s2的不为空或空串时，声明i、j指针，此处的j指针有两重含义：

  1. 表示拿哪个位置（即j位置）的字符和i-1位置的字符比较；
  2. 也表示当前最长匹配前后缀的长度的下一字符位置。

从i === 2处开始迭代，判断i - 1位置处字符与j位置处字符：

  • 若匹配，则更新next[i] = j + 1，并步增i、j指针；
  • 若不匹配：
    • 当j > 0时，将j指针赋值为next[j]的值，即j指针前跳至前一个前后缀匹配的最大长度处（加速操作）；
    • 当j === 0时，说明next找完了，即不存在匹配前后缀，故设为0，并步增i指针。

代码实现： ​

JavaScript
const getNext = s2 => {
  const len = s2.length
  const next = Array(len).fill(0)
  let [i, j] = [2, 0]
  while (i < len) {
    if (s2.charAt(i - 1) === s2.charAt(j)) {
      next[i++] = ++j
    } else if (j === 0) {
      next[i++] = 0
    } else {
      j = next[j]
    }
  }
  return next
}

const KMP = (s1, s2) => {
  if (!s1 || !s2 || !s1.length || s1.length < s2.length) return -1
  const [ret, next] = [[], getNext(s2)]
  let i = j = 0
  while (i < s1.length) {
    if (s1.charAt(i) === s2.charAt(j)) {
      i++
      j++
    } else if (j === 0) {
      i++
    } else {
      j = next[j]
    }
    if (j === s2.length) {
      return i - j
    }
  }
  return ret
}

若s2是s1的子串，现在需要求出所有s2在s1中匹配位置的起始位置？

代码实现： ​

JavaScript
const KMP = (s1, s2) => {
  if (!s1 || !s2 || !s1.length || s1.length < s2.length) return -1
  const [ret, next] = [[], getNext(s2)]
  let i = j = 0
  while (i < s1.length) {
    if (s1.charAt(i) === s2.charAt(j)) {
      i++
      j++
    } else if (j === 0) {
      i++
    } else {
      j = next[j]
    }
    if (j === s2.length) {
      ret.push(i - j)
      j = 0
    }
  }
  return ret
}