KMP 算法

在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词P的出现位置。

传统的匹配算法

对于字符串"abcdabcabcd abcdabdd"，从中查找匹配串"abcdabd"的位置，最传统的方法是暴力搜索法

......

......

以下是实现代码：

function search(str, pattern) {
  let i = j = 0
  while(i < str.length) {
    if(str[i+j] !== pattern[j]) {
      j = 0
      i++
    }else {
      j++
    }
    if(j === pattern.length) {
      return i
    }
  }
  return -1
}

暴力匹配的时间复杂度为 O(nm)，其中 n 为 str 的长度，m 为 pattern 的长度，这样的时间复杂度无法满足我们的需求。

KMP 算法

首先，主串"BBC ABCDAB ABCDABCDABDE"的第一个字符与模式串"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以模式串后移一位。

因为B与A又不匹配，模式串再往后移。

就这样，直到主串有一个字符，与模式串的第一个字符相同为止。

接着比较主串和模式串的下一个字符，还是相同。

直到主串有一个字符，与模式串对应的字符不相同为止。

这时，最自然的反应是，将模式串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实是已经知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，而是继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对模式串，设置一个跳转数组next，这个数组是怎么计算出来的，后面再介绍，这里只要知道根据数组里设置的值进行位移就行。。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。根据跳转数组可知，不匹配处D的next值为2，因此接下来从模式串下标为2的位置开始匹配。

因为空格与Ｃ不匹配，C处的next值为0，因此接下来模式串从下标为0处开始匹配。

因为空格与A不匹配，此处next值为-1，表示模式串的第一个字符就不匹配，那么直接往后移一位。

逐位比较，直到发现C与D不匹配。于是，下一步从下标为2的地方开始匹配。

逐位比较，直到模式串的最后一位，发现完全匹配，于是搜索完成。

实现代码如下：

function search(str, pattern) {
  let next = getNext(pattern) //假设我们已经能通过getNext生成next 数组，后面再去实现它
  let i = j = 0
  while(i < str.length) {
    if(j === -1 || str[i] === pattern[j]) {
      j++
      j++
    }else {
      j = next[j]
    }
    if(j === pattern.length) {
      return i - j
    }
  }
  return -1
}

next数组

这里先讲一下字符串的"前缀"和"后缀"。对于字符串"jirenguji":

• 前缀："j","ji","jir","jire","jiren","jireng","jirengu","jirenguj"
• 后缀: "i","ji","uji","guji","nguji","enguji","renguji","irenguji"

其中前缀不包含最后一个字符，后缀不包含第一个字符。字符串"ABCDAB"的相同前后缀为"AB"。

next数组的求解基于“前缀”和“后缀”，即next[i]等于匹配串从第1到第i-1个字符构成的字符串最长的相同前后缀的长度

1. i = 0，A前面没字符串，作为模式串的首字符，我们统一为next[0] = -1；
2. i = 1，前面的字符串为A，其最长相同前后缀长度为0，即next[1] = 0；
3. i = 2，前面的字符串为AB，其最长相同前后缀长度为0，即next[2] = 0；
4. i = 3，前面的字符串为ABC，其最长相同前后缀长度为0，即next[3] = 0；
5. i = 4，前面的字符串为ABCD，其最长相同前后缀长度为0，即next[4] = 0；
6. i = 5，前面的字符串为ABCDA，其最长相同前后缀长A，即next[5] = 1；
7. i = 6，前面的字符串为ABCDAB，其最长相同前后缀为AB，即next[6] = 2；

那么，为什么根据最长相同前后缀的长度就可以实现在不匹配情况下的跳转呢？举个代表性的例子：假如i = 6时不匹配，此时我们是知道其位置前的字符串为ABCDAB，仔细观察这个字符串，首尾都有一个AB，既然在i = 6处的D不匹配，我们为何不直接把i = 2处的C拿过来继续比较呢，因为都有一个AB啊，而这个AB就是ABCDAB的最长相同真前后缀，其长度2正好是跳转的下标位置。

那如何写getNext函数来实现所需要的计算结果呢

function getNext(pattern) {
  let next = [-1]
  let j = -1, i = 0 
  while(i < pattern.length - 1) {
    if(j === -1 || pattern[i] === pattern[j]) {
      i++
      j++
      next[i] = j
    }else {
      j = -1
    }
  }
}

代码很简单，但理解起来有些晦涩。模拟代码的执行看一下中间过程，你就能理解

初始：P = "ABCDABD", j = -1, i = 0, next = [-1, undefined, undefined, undefined, undefined, undefined, undefined]

第一轮：因为 j === -1，所以 i++, j++, next[i] = j。此时 i = 1, j = 0, next[1] = 0

第二轮：P[i]（即 P[1]）的值不等于 P[j]（即P[0])，所以 j = -1

第三轮：因为 j === -1，所以 i++, j++, next[i] = j。此时 i = 2, j = 0, next[2] = 0

第四轮：P[i]（即 P[2]）的值不等于 P[j]（即P[0])，所以 j = -1

第五轮：因为 j === -1，所以 i++, j++, next[i] = j。此时 i = 3, j = 0, next[3] = 0

第六轮：P[i]（即 P[3]）的值不等于 P[j]（即P[0])，所以 j = -1

第七轮：因为 j === -1，所以 i++, j++, next[i] = j。此时 i = 4, j = 0, next[4] = 0

第八轮：P[i]（即 P[4]）的值等于 P[j]（即P[0])，所以 i++, j++,next[i] = j。此时 i = 5, j = 1, next[5] = 1

第九轮：P[i]（即 P[5]）的值等于 P[j]（即P[1])，所以 i++, j++,next[i] = j。此时 i = 6, j = 2, next[6] = 2

全部代码

function search(str, pattern) {
  let next = getNext(pattern) 
  let i = j = 0
  while(i < str.length && j < pattern.length) {
    if(j === -1 || str[i] === pattern[j]) {
      j++
      j++
    }else {
      j = next[j]
    }
  }
  if(j === pattern.length) {
    return i - j
  }
  return -1
}

function getNext(pattern) {
  let next = [-1]
  let j = -1, i = 0 
  while(i < pattern.length - 1) {
    if(j === -1 || pattern[i] === pattern[j]) {
      i++
      j++
      next[i] = j
    }else {
      j = -1
    }
  }
  return next
}

参考

• 本文图片和部分内容拷贝至刘毅-KMP算法
• 阮一峰-KMP算法