字符串搜索 - KMP算法 - 《数据结构与算法》

基于DFA实现
- 构建DFA
- 最终实现代码
基于PMT实现
- 构建next
参考资料

KMP算法的基本思路是当出现不匹配时，利用匹配失败后的信息避免将指针会退到所有这些一直的字符之前。核心是提前判断如何重新开始查找，而这种判断只取决于模式本身。KMP有两种实现方式。一种是基于确定有限状态自动机机(Determinstic Finite Automata, DFA)的KMP实现，另一种是基于部分匹配表(Parital Match Table, PMT)的KMP实现。

定义：文本字符串txt，文本指针i，模式字符串pat，模式指针j

基于DFA实现

KMP算法中，不会回退文本指针i，而是使用一个数组dfa[][]来记录匹配失败时模式指针j应该回退多远。

dfa[c][j] 表示状态j，模式串中该字符串的索引值，和字符c匹配转换的下一个状态。也就是指向j的下一个值。

图中所示，每个状态都表示模式串中的每个字符的索引值，这些转换中只有一条匹配转换（从j到j+1，箭头从左指向右），其他都是非匹配转换（箭头从右指向左）。

当我们在标记为j的状态中检查文本串中的第i个字符，自动机的处理过程为：沿着转换dfa[txt[i]][j]前进并继续检查下一个字符（i+1）。对于一个匹配的转换，就向右移动一位，因为dfa[pat[j]][j]的值总是指向j+1；对于一个非匹配转换,就向左移动。

自动机从状态0开始，每次从左向右读取文本串中的一个字符，并移动到一个新状态，如果自动机到达了停止状态M，那么就在文本串中找到了和模式串相匹配的一段子串（称这种状态为确定有限状态自动机识别了该模式）。如果在文本串扫描结束都未能达到状态M，就意味着文本串中不存在该字符串。每个模式串都对应着一个自动机（dfa[][]）。

function search(pat, txt) {
    const M = pat.length;
  const N = txt.length;
  const dfa = buildDfa(pat);
  let i,j;
  for (i = 0, j = 0; i < N && j < M; i += 1) {
      j = dfa[txt.charCodeAt(i)][j];
  }
  if (j === M) return i - M;
  return -1;
}

构建DFA

function buildDfa(pat) {
    const M = pat.length;
  const R = 256;
  const dfa = new Array(R).fill(0).map(
      () => new Array(M).fill(0),
  );
  // base case
  dfa[pat.charCodeAt(0)][0] = 1;
  for (let X = 0, j = 1; j < M; j += 1) {
      for (let c = 0; c < R; c += 1) {
        dfa[c][j] = dfa[c][X];
    }
    dfa[pat.charCodeAt(j)][j] = j + 1;
    X = dfa[pat.charCodeAt(j)][X];
  }
  return dfa;
}

最终实现代码

function search(pat, txt) {
  const M = pat.length
  const N = txt.length
  const R = 256
  // 构建dfa
  const dfa = new Array(256).fill(0).map(() => new Array(M).fill(0))
  // base case
  dfa[pat.charCodeAt(0)][0] = 1
  for (let X = 0, j = 1; j < M; j += 1) {
    for (let c = 0; c < R; c += 1) {
      // 匹配失败的情况，完全匹配失败，完全回退后重新匹配还会到达重启位置X
      // 因此可以将dfa[][X]复制给dfa[][j]
      dfa[c][j] = dfa[c][X]
    }
     // 匹配成功的情况
    dfa[pat.charCodeAt(j)][j] = j + 1
    // 更新重启位置X。因为X < j，所以可以从已构造的DFA部分来更新X的值，
    // dfa[needle.charCodeAt(j)][X]会指向X的下一个值。
    X = dfa[pat.charCodeAt(j)][X]
  }
  let i, j
  for (i = 0, j = 0; i < N && j < M; i += 1) {
    j = dfa[txt.charCodeAt(i)][j]
  }
  if (j === M) return i - M
  return -1
}

图片来源于《算法》

基于PMT实现

首先解释下什么是字符串的前缀和后缀。如果字符串A和B，存在A = BS，其中S为任意非空字符串，那么称B为A的前缀。如”Harry”的前缀包括{“H”, “Ha”, “Har”, “Harr”}，把所有前缀组成的集合，成为字符串的前缀集合。同样可以定义A = SB，其中S是任意的非空字符串，那就称B为A的后缀，”Potter”的后缀包括{“otter”, “tter”, “ter”, “er”, “r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

index	0	1	2	3	4	5	6	7
char	a	b	a	b	a	b	c	a
pmt	0	0	1	2	3	4	0	1
next	-1	0	0	1	2	3	4	0

以模式串”abababca”为例，模式串长度为8，PMT就会有8个值。PMT中的值是字符串的前缀集和后缀集的交集中最长元素的长度。比如，对于字符串”ababa”，它的前缀集为{“a”, “ab”, “aba”, “abab”}，它的后缀集为{“baba”, “aba”, “ba”, “a”}，两个合集的交集为{“aba”, “a”}，其中最长的元素为”aba”，长度为3。

有了这个表之后就可以加速查找字符串了。在文本串"ababababca"中查找模式串"abababca“，如果在j处字符匹配不上，那么有模式串PMT的性质可知，文本串中i指针之前的前PMT[j-1]位必定和模式串的第0位至第PMT[j-1]位是相同的。这是因为文本串在i处匹配失败，也就意味着文本串从i-j到i-1这一段是与模式串的0到j-1这一段是完全相同。模式串从0到j-1，也就是"ababab"，其前缀集和后缀集的交集最长元素为"abab"，长度为4。所以可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持**i**指针不动，然后将**j**指针指向模式字符串的**PMT[j −1]**位即可。

有了上面的思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在j位失配，那么影响j指针回溯的位置的其实是第j-1位的 PMT 值，所以为了编程的方便，我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。同时也为了编程方便，把PMT向右偏移时，第0位的值设置为-1，如上面表格所示。

具体程序如下：

function search(pat, txt) {
  const M = pat.length
  const N = txt.length
  const next = getNext(pat)
  let i = 0
  let j = 0
  while (i < N && j < M) {
    if (j === -1 || pat.charCodeAt(j) === txt.charCodeAt(i)) {
      // 匹配成功，i,j都位移一位
      i++
      j++
    } else {
      // 匹配失败，j回退到第next[j]位，i不变，继续对比
      j = next[j]
    }
  }
  if (j === M) return i - M
  return -1
}

构建next

那么如何构建next数组呢？其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式串为文本串，以模式串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。在任一位置，能匹配的最长长度就是当前位置的next值。

function getNext(pat) {
  const M = pat.length
  const next = new Array(M).fill(0)
  next[0] = -1
  let i = 0
  let j = -1
  while (i < M) {
    if (j === -1 || pat.charCodeAt(i) === pat.charCodeAt(j)) {
      // pmt[i] == next[i+1] == j+1
      i++
      j++
      next[i] = j
    } else {
      // j == pmt[j-1] == next[j]
      j = next[j]
    }
  }
  return next
}

最终代码如下

function getNext(pat) {
  const M = pat.length
  const next = new Array(M).fill(0)
  next[0] = -1
  let i = 0
  let j = -1
  while (i < M) {
    if (j === -1 || pat.charCodeAt(i) === pat.charCodeAt(j)) {
      next[++i] = ++j
    } else {
      j = next[j]
    }
  }
  return next
}
function search(pat, txt) {
  const M = pat.length
  const N = txt.length
  const next = getNext(pat)
  let i = 0
  let j = 0
  while (i < N && j < M) {
    if (j === -1 || pat.charCodeAt(j) === txt.charCodeAt(i)) {
      i++
      j++
    } else {
      j = next[j]
    }
  }
  if (j === M) return i - M
  return -1
}

KMP算法

基于DFA实现

构建DFA

最终实现代码

基于PMT实现

构建next

参考资料