KMP算法

KMP 算法详解

KMP 算法全称为 Knuth-Morris-Pratt 算法，由 Knuth 和 Pratt 在1974年构思，同年 Morris 也独立地设计出该算法，最终由三人于1977年联合发表。是一个著名的字符串匹配算法，效率很高，但有点复杂。
KMP 算法目的是在一个字符串 s 中，查询 s 是否包含子字符串 p，若包含，则返回 p 在 s 中起点的下标。

举一个简单的例子，在字符串 s = abcabdabccbd 中查找子字符串 p = dabc

对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。

function findIndex (s, p) {
  const sLen = s.length
  const pLen = p.length

  for (let i = 0; i <= sLen - pLen; i++) {
    let j = 0
    for (j; j < pLen; j++) {
      if (p[j] !== s[i + j]) break
    }
    if (j === pLen) return i
  }
  return -1
}

findIndex('abcabdabccbd', 'dabc') // 5

这种朴素的暴力的算法复杂度为 O(m×n)，其中 m 和 n 分别是 p 和 s 的长度。

KMP 算法可以方便地简化这一查询的时间复杂度，达到 O(m+n)。

1. PMT 序列

PMT 序列是 KMP 算法的核心，即 Partial Match Table（部分匹配表）

char	a	b	c	a	b	d	a	b	c	c	b	d
index	0	1	2	3	4	5	6	7	8	9	10	11
PMT	0	0	0	1	2	0	1	2	3	0	0	0

生成PMT序列

function genMPT (p) {
  let now = 0
  let index = 1
  const arrMPT = [0]
  while (index < p.length) {
    if (p[now] === p[index]) {
      now++
      index++
      arrMPT[index] = now
    } else if (now) {
      now = arrMPT[now - 1]
    } else {
      arrMPT.push(0)
      index++
    }
  }
  return arrMPT
}

2. 算法主体

知道了 PMT 序列的含义，就来看算法的主体。

1. tar 存储 s 的下标，从 0 开始，若 tar > s.length() - 1， 代表匹配失败；
2. pos 存储 p 的下标，从 0 开始，若 s[tar] != p[pos]，则 pos 走到下一个可能匹配的位置。

function findIndexByKMP (s, p) {
  let tar = 0
  let pos = 0

  const mpt = genMPT(p)

  while (tar < s.length) {
    if (s[tar] === p[pos]) {
      tar++
      pos++
    } else if (pos) {
      pos = mpt[pos - 1]
    } else {
      tar++
    }
    if (pos === p.length) {
      return tar - p.length
    }
  }
  return -1
}