本文已参加「新人创造礼」活动，一同开启掘金创造之路。

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算法（动态图解、c++、java）

简单的匹配代码

从算法过程部分不难看出：

  1. i 的回退方位为 i – j + 1 。
  2. j 的回退方位为 0 。

c++代码如下（示例）：

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代码如下（示例）：

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)O(n + m) 。

2. 最坏状况：

例如：S = “aaaab” ，T = “ab”。

此刻，在最终一次匹配前，i、j 一直在回退。

平均时刻复杂度为 O(nm)O(n m) 。

总结

  • 在示例比较中，其中一步为：
    【数据结构】串-模式匹配BF算法（动态图解、c++、java）
  • 通过形式匹配BF算法，i、j 回退为：
    【数据结构】串-模式匹配BF算法（动态图解、c++、java）
  • 但通过调查，咱们可以发现，咱们完全可以直接这么比较：

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

  • i 不回退，只 j 回退，这样时刻复杂度就削减一些。（ 注：j 前串已和 i 前串持平 ）

此方法便是 KMP算法 。

本来打算明日发 KMP 的，但是有些工作需要处理一下，明日更不了 KMP 了 。

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

关注大众号，感受不同的阅读体验

下期预告：数据的次序存储