字符串匹配算法有很多种,现在为大家带来 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
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));
本文在写作过程中参考了很多优秀的文章和视频,在此对他们的帮助表示感谢。
如果你在看本文时发现有不懂的地方或者是有不正确的地方,欢迎评论告诉我,我会继续修订。