Sunday 算法快速入门

Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配算法，该算法的核心思想与 BM 算法类似。

通过本文章我可以学到什么

1. Sunday 算法

   • 思想

   • 实现

   • 优点

   • 局限性

举个栗子

Sunday 算法匹配方式如下：

例 1

• 令字符串 txt 为 ABCDABA
• 令模式串 pat 为 ABA

则刚开始匹配时 txt 与 pat 左端对齐

此时我们从 pat 的左端开始向右匹配，当匹配到第三位时 txt 与 pat 的内容不同：

接着检查 txt 中 pat 的长度下一位字母在 pat 中有没有出现过。

发现 $D$ 并没有在 pat 中出现，便将整个 pat 向后移动 $len (pat) + 1$ 位：

此时便匹配成功。

例 2

• txt = ABBBABBABA
• pat = ABA

初始状态：

匹配时发现在第 $4$ 位时 txt 与 pat 不一样，于是便比较 txt 的 $len (pat) + 1$ 位，发现 $A$ 在 pat 中出现过，于是便将该处 $A$ 与 pat 中最接近末尾的 $A$ 对齐：

匹配时发现匹配失败了，于是检查下一位 $B$ 在 pat 中出现过，将它与 pat 中最靠近末尾的 $B$ 对齐：

检查下一位，对齐：

匹配成功。

算法思想

• 从头开始匹配
• 匹配到不一样时对比 txt 中整个 pat 长度的下一位是否在 pat 中出现过
  • 出现则跳到离末端最近
  • 未出现则整个 pat 跳过

时间复杂度

$O(n)$

代码实现

令 nowTxt 代表目前 txt 中匹配对应 pat 的首字母所在的位置，nowPat 为匹配到的 pat 的第几位。

pat 匹配

while (txt[nowTxt + nowPat] == pat[nowPat]) {
  ++nowPat; // 对应位置匹配后将 检测的位置 向后移动

  if (nowPat == pat.length()) { // 完全匹配整个pat字符串则返回对应的pat所在位置
    return nowTxt;
    break;
  }
}

移动位数

array<int, 26> sundayArray; // 一共26个字母，则开数组为26即可（可以根据自己需要进行修改）
inline void getSundayArray(const string &pat) {
  int len = pat.length(); // 获取pat的长度

  fill(sundayArray.begin(), sundayArray.end(), -1); // 初始化数组为 -1

  for (int i = len - 1, cnt = 0; i >= 0 && cnt < 26; ++i) { // 倒叙枚举，保证正确性（使对应字母离尾端的距离位最小值）
    int j = pat[i] - 'A'; // 获取pat对应位上的字母编号

    if (sundayArray[j] == -1) { // 如果之前并未修改，说明之前并没有出现对应字母
      sundayArray[j] = len - i; // 修改
      ++cnt; // 计数，如果已经拥有26个字母则跳出
    }
  }
}

进行匹配

inline int sunday(const string &txt, const string &pat) {
  int n = txt.length(); // 获取txt长度
  int m = pat.length(); // 获取pat长度

  int nowTxt = 0, nowPat;   // 定义变量（指针）
  while (nowTxt + m <= n) { // 直到不能匹配为止
    nowPat = 0;             // 初始化pat对应位置位开头（即0）

    while (txt[nowTxt + nowPat] == pat[nowPat]) {
      ++nowPat;

      if (nowPat == m) {
        return nowTxt;
      }
    }

    if (nowTxt + m >= n) { // 超限则输出无解(-1)
      return -1;
    }

    if (sundayArray[txt[nowTxt + m] - 'A'] != -1) {
      nowTxt += sundayArray[txt[nowTxt + m] - 'A'];
    } else {
      nowTxt += m + 1;
    }
  }
}

局限性

当字符串 txt 与模式串 pat 具有特定的关系时，Sunday 算法的时间复杂度可能会退化为 $O (n \times m)$