【数据结构】串-模式匹配BF算法(动态图解、c++、java)

语言: CN / TW / HK

本文已参与「新人创作礼」活动,一起开启掘金创作之路。

GitHub同步更新(已分类)Data_Structure_And_Algorithm-Review

公众号:URLeisure 的复习仓库 (点击可见公众号二维码)

提示:以下是本篇文章正文内容,下面案例可供参考


什么是模式匹配?

  • 字串的定位运算称为串的模式匹配串匹配

  • 假设有两个串 S、T,设 S 为主串,也称正文串;T 为子串,也称模式。

  • 在主串S中查找与模式T相匹配的子串,如果查找成功,返回匹配的子串第一个字符在主串中的位置。

  • 最笨的办法就是穷举S的所有子串,判断是否与T匹配,该算法称为BF(Brute Force)算法

模式匹配 BF 算法步骤(动图)

  1. 从 S 第0个字符开始,与T第0个字符比较。 如果相等,继续比较下一个字符,否则跳转向下一步;
  2. 从 S 第1个字符开始,与T第0个字符比较。 如果相等,继续比较下一个字符,否则跳转向下一步;
  3. 从 S 第2个字符开始,与T第0个字符比较。 如果相等,继续比较下一个字符,否则跳转向下一步; ...

  1. 如果 T 比较完毕,则返回 T 在 S 中第一个字符出现的索引(从零开始);
  2. 如果 S 比较完毕,则返回 -1,说明 T 在 S 中未出现。

设,S = “abcabdcababdcabeac”,T = “abdcabe”,求子串 T 在主串 S 中位置。

先来一遍文字说明,再上图解。

  1. S[0] == T[0] , S[1] == T[1] , S[2] != T[2] , 跳转下一步;
  2. S[1] != T[0] , 跳转下一步;
  3. S[2] != T[0] , 跳转下一步;
  4. S[3] == T[0] , S[4] == T[1] , S[5] == T[2] , S[6] == T[3] , S[7] == T[4] , S[8] == T[5] , S[9] != T[6] 跳转下一步;
  5. S[4] != T[0] , 跳转下一步;
  6. S[5] != T[0] , 跳转下一步;
  7. S[6] != T[0] , 跳转下一步;
  8. S[7] == T[0] , S[8] == T[1] , S[9] != T[2] , 跳转下一步;
  9. S[8] != T[0] , 跳转下一步;
  10. S[9] == T[0] , S[10] == T[1] , S[11] == T[2] , S[12] == T[3] , S[13] == T[4] , S[14] == T[5] , S[15] == T[6] ;
  11. T 比较完毕,返回 9。

BF

简单的匹配代码

从算法步骤部分不难看出:

  1. i 的回退位置为 i - j + 1
  2. j 的回退位置为 0

c++代码如下(示例):

```cpp int Index_BF(string s, string t) { int i = 0, j = 0; int lens = s.length(); int lent = t.length(); while (i < lens && j < lent) { if (s[i] == t[j]) { i++, j++; continue; } else { i = i - j + 1; j = 0; } }

if (j == lent) {
    return i - j;
}
return -1;

} ```

java代码如下(示例):

java public static int index_bf(String s, String t){ int i = 0; int j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) == t.charAt(j)) { i++; j++; } else { j = 0; i = i - j + 1; } } if (j == t.length()) { return i - j; } return -1; }

BF 算法复杂度分析

1. 最好情况:

例如:S = "abcdefg" ,T = “def”。

此时,在匹配时,i 、j 都不需要回退。

平均时间复杂度为 $O(n + m)$

2. 最坏情况:

例如:S = "aaaab" ,T = “ab”。

此时,在最后一次匹配前,i、j 一直在回退。

平均时间复杂度为 $O(n × m)$


总结

  • 在示例比较中,其中一步为: 示例
  • 通过模式匹配BF算法,i、j 回退为: BF
  • 但通过观察,我们可以发现,我们完全可以直接这么比较:

KMP * i 不回退,只 j 回退,这样时间复杂度就减少一些。( 注:j 前串已和 i 前串相等

此方法便是 KMP算法


本来打算明天发 KMP 的,但是有些事情需要处理一下,明天更不了 KMP 了 。

只能先发一篇存稿了,下下一篇绝对 KMP。


关注公众号,感受不同的阅读体验

下期预告:数据的顺序存储