字符串匹配

Posted on Edited on Symbols count in article: 2.2k Reading time ≈ 2 mins.

BF(Brute Force)算法

  • BF是最符合人类直觉的字符串匹配算法，但是主串的下标i经常要往回走，无法利用已匹配信息，效率不够好 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int bruteForce(const string& t, const string& p) {
        int i = 0, j = 0;
        // i和j都是非负数，所以可以和无符号直接比较
        while (i < t.size() && j < p.size()) {
            if (t[i] == p[j]) {
                ++i; ++j;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == p.size())
            return i - j;
        else
            return -1;
    }

KMP算法

  • 思想：“利用已部分匹配的信息，保持i指针不回溯，通过修改j指针，让模式串尽量移动到有效的位置”
  • 定义next数组： next[j] = d 表示当 t[i] != p[j] 时，j下一次匹配的位置。注意到，下标从0开始，d值实际上是下标j前的最长前后缀子串的长度
  • 求取next的过程本身就是p串与自己匹配的过程
    1. 当 p[i]==p[j] ，则 p[++i] = ++j
    2. 当 p[i]!=p[j] ，则利用前面已求得的next数组，j=next[j] ；直到无法找到，此时 j=-1 ，自动进入第一个if语句，此时i往后走一步，妙 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      vector<int> getNext(const string& p) {
          int n = p.size();
          vector<int> next(n);
          next[0] = -1;
          int i = 0, j = -1;
          // !!! i < n 则会在下面越界，因为0已经求过了，循环只会进行n-1次
          while (i < n - 1) {
              if (j == -1 || p[i] == p[j]) {
                  ++i, ++j;
                  next[i] = j;
              } else {
                  j = next[j];
              }
          }
          return next;
      }

      int KMP(const string& t, const string& p) {
          vector<int> next = getNext(p);
          int n = t.size(), m = p.size();
          int i = 0, j = 0;
          // !!! j可以为负数，和无符号比较会转换为无符号比较法(南辕北辙)
          while (i < n && j < m) {
              if (j == -1 || t[i] == p[j]) {
                  ++i; ++j;
              } else {
                  j = next[j];
              }
          }
          if (j == p.size())
              return i - j;
          else
              return -1;
      }

KMP之Next优化

  • 比如[ A B A B ]这个串，按照上面所述KMP得到的结果是[-1, 0, 0, 1]，然而，例如匹配的是[ A B A B D E]，在下标为3处失败了，next指导去下标1处继续匹配，但是，下标1和下标3都是B，没有必要再进行比较了。诸如此类的例子还有[ A A A A B]，用上述KMP得到的next是[-1, 0, 1, 2, 3]
  • 方法就是在 ++i, ++j 后加一步判断，本来直接 next[i]=j 但是如果 p[i]==p[j] 则如果以后匹配 p[i] 失败，则匹配 p[j] 肯定也失败啊，所以如果两者相等，直接 next[i] = next[j] 。此时的结果对于[ A B A B ]产生的是[-1, 0, -1, 0]；对于[ A A A A B]产生的是[-1, -1, -1, -1, 3]
  • 加三行代码就行了 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    vector<int> getNext(const string& p) {
        int n = p.size();
        vector<int> next(n);
        next[0] = -1;
        int i = 0, j = -1;
        while (i < n - 1) {
            if (j == -1 || p[i] == p[j]) {
                ++i, ++j;
                if (p[i] == p[j]) // new 
                    next[i] = next[j]; // new 
                else // new
                    next[i] = j;
            }
            else {
                j = next[j];
            }
        }
        return next;
    }

    int KMP(const string& t, const string& p) {
        vector<int> next = getNext(p);
        int n = t.size(), m = p.size();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || t[i] == p[j]) {
                ++i; ++j;
            }
            else {
                j = next[j];
            }
        }
        if (j == p.size())
            return i - j;
        else
            return -1;
    }

参考资料

  • 博客园博主：sofu6