阅读 489

字符串匹配算法之 BF 和 KMP 讲解

字符串匹配算法有很多种,现在为大家带来 BF 和 KMP 的讲解,其中讲 BF 是为了与 KMP 算法做一个对比,让本文有由浅到深这样的一个递进关系。

BF 算法

查找一个字符串是否在另一个字符串中,我们最容易想到的方法就是使用两个循环来解决,这种算法就叫做 BF,全称是 Brute-Force,中文翻译为:暴力匹配。

这是 BF 匹配的过程

BF 算法的思路

首先设文本串为 S,模式串为 P,假设文本串匹配到 i 位置,模式串匹配到 j 位置。

1、如果当前字符匹配成功(即 S[i] == P[j]),则 i++,j++,继续匹配下一个字符;

2、如果失配(即 S[i] != P[j]),这时令 i = i - (j - 1),j = 0。

因为 i 的位置根据上述公式计算后,往前回退了,所以叫做 i 回溯。

至于 i = i - (j - 1) 这个公式是如何推导出来的,可以这么理解,你往前走了 j 步,要退回到原位,那就往回走 j 步就可以了,如果是要在原来的位置上再进一步,那就往回走 j - 1 步就可以了。

当然你也可以写成 i = i - j + 1 表示回到原点后再往前走一步,更容易理解。

3、匹配成功后,返回 i - j,可以理解为往前走那么多步后再回到原点。

BF 算法代码实现

这里我是用 JavaScript 实现的:

// for 循环的写法
let str = "abdfadfadfgrereabdgfa";
let pattern = "dfadfg";

function BF(S, P) {
  for (let i = 0; i < S.length;) {
    for (let j = 0; j < P.length;) {
      if (S[i] === P[j]) {
        i++;
        j++;
      } else {
        i = i - (j - 1);
        break;
      }
      if (j === P.length) {
        return i - j;
      }
    }
  }
  return -1;
}

console.log(BF(str, pattern));
复制代码
// while 循环的两种写法
let str = "ababcdaaabbc ababc";
let pattern = "cda";

function BF(S, P) {
  let i = 0; let j = 0;
  while(i < S.length) {
    if (S[i] === P[j]) {
      i++;
      j++;
    } else {
      i = i - (j - 1);
      j = 0;
    }
    if (j === P.length) {
      return i - j;
    }
  }
  return -1;
}

console.log(BF(str, pattern));

function BF2(S, P) {
  let i = 0; let j = 0;
  while(i < S.length && j < P.length) {
    if (S[i] === P[j]) {
      i++;
      j++;
    } else {
      i = i - (j - 1);
      j = 0;
    }
  }
  if (j === P.length) {
    return i - j;
  }
  return -1;
}

console.log(BF2(str, pattern));
复制代码

KMP 算法

接下来为大家介绍 KMP 算法,KMP 的全称是 Knuth-Morris-Pratt , 中文名:克努斯-莫里斯-普拉特,这个算法是由 D.E.Knuth 和 V.R.Pratt 在 1974 年构思,同年 J.H.Morris 也独立地设计出该算法,最终由三人于 1977 年联合发表。属于字符串匹配算法中比较重要的一个算法。

Donald Knuth

Donald Knuth

BF 和 KMP 的区别

我们来看一张图对比一下 BF 和 KMP 的区别:

可以看到在失配时, BF 的 i 回溯的位置会很远,同时 j 也会回溯到 0 位置;

而 KMP 的做法是 i 保持不变,只需要按条件设置好 j 的位置后,继续往下匹配就可以了。

BF 的复杂度为 O(n*m),KMP 的复杂度为 O(n+m),所以 KMP 是一种比较高效的字符串匹配算法。

通过这张对比图,我们知道,KMP 高效的原因就在于,只需要移动模式串就可以了。

那么如何找到一种办法来达到这个目的呢?

PMT 数组的作用

KMP 提出了一个叫 PMT 的数组来达到这个目的,它的全称是 Partial-Match-Table,中文翻译为:部分匹配表。

这个表是根据模式串生成出来的,里面记录的就是当失配后,模式串需要移动的位置。

我们看一下这个 PMT 长什么样:

可以看到模式串中的每一个字符都对应了一个数字,这个数字就是这个字符的 PMT 值,前面也说过这个 PMT 值就代表了当失配后,模式串需要移动的位置。

如何计算 PMT

那么如何计算出 PMT 呢?答案是通过计算字符串的前后缀来得出:

第一步,我们需要找到模式串的所有子串,需要按从前往后的顺序来写出所有子串(想象成一个集合,所以也会包括自己本身)。

第二步,找到每一个子串的前后缀组合,前缀是不包含最后一个字符的子串集合,后缀是不包含第一个字符的子串集合,然后找到前后缀集合的交集,最后找到交集中字符串长度最长的那个,这个字符串的长度,就是我们需要的 PMT 值。

通过上图可以看到,其实模式串中每个字符对应的 PMT 值,就是这个子串的前后缀共有集合中,字符串长度最大的值。

最大前后缀的小练习

接下来做一些找共有最大前后缀的小练习吧:

从这些练习中能发现什么规律呢?没错,模式串的最大前后缀分别只出现在开头和结尾,而且它们都是相等的。

那,这又代表了什么意思呢?

到此为止,你应该能明白 PMT 的真正作用了吧!

KMP 的匹配过程

我们来看一遍 KMP 的匹配过程:

解释一下图中标记的三个点:

1、图中 v 代表 PMT。

2、失配时,找 j - 1 位的 PMT 值,图中是 2,即此时 PMT[j - 1] = 2。图中标红的字符,就是已经匹配过的子串 dfadf 中的前后缀。

3、接下来保持 i 不变,把 j 的值设为 PMT[j-1],也就是 2,这步操作就是把模式串的前缀对齐了已匹配串的后缀,这就是所说的充分利用已知信息来提高匹配效率。

PMT 数组用途总结

共有最大前后缀分别处于原字符串中的开始和结尾处,我们可以利用这个性质来记录已知信息,也就是已匹配过的字符,如果有大于 0 的 PMT 值,说明已匹配过的地方有需要再匹配避免遗漏的,否则都是 0 的话,j 就简单地回溯到 0 就可以了,这就是 PMT 数组的用途。

生成 PMT 的思路

知道 PMT 的用途后,那我们如何使用程序来生成 PMT 呢?

思路:

1、

2、

3、

4、

5、从匹配进入到失配状态时 i 的回溯稍微有点复杂:

6、这时因为 i = 0 了,就可以进行比较了,如果 i != 0 那么还要继续重复第 5 和第 6 的过程。

程序计算的大致过程就是这样的,你可以再做几个小练习来巩固一下:

KMP 算法的代码实现

下面就是根据以上思路用程序来实现算法了:

let str = "abdfadfadfgrereabdgfa";
let pattern = "dfadfg";

// 求 PMT
function partialMatchTable(P) {
  // 初始条件
  let PMT = [], i = 0, j = 1;
  PMT[0] = 0;
  while(j < P.length) {
    if (P[i] === P[j]) {
      i++;
      PMT[j] = i;
      j++;
    } else {
      if (i !== 0) {
        i = PMT[i - 1];
      } else {
        PMT[j] = 0;
        j++;
      }
    }
  }
  return PMT;
}

// KMP 主体
function KMP(S, P) {
  let i = 0, j = 0, TMP = partialMatchTable(P);
  while (i < S.length && j < P.length) {
    if (S[i] === P[j]) {
      i++;
      j++;
    } else {
      if (j !== 0) {
        j = TMP[j - 1];
      } else {
        i++;
      }
    }
  }
  if (j === P.length) {
    return i - j;
  }
  return -1;
}
console.log(KMP(str, pattern));
复制代码

本文在写作过程中参考了很多优秀的文章和视频,在此对他们的帮助表示感谢。

如果你在看本文时发现有不懂的地方或者是有不正确的地方,欢迎评论告诉我,我会继续修订。

参考资料

  1. www.bilibili.com/video/av324…
  2. www.cnblogs.com/rubylouvre/…
  3. www.zhihu.com/question/21…
  4. blog.csdn.net/v_july_v/ar…
  5. github.com/mission-pea…
  6. www.ruanyifeng.com/blog/2013/0…