Sunday 算法

基本概念

Sunday 算法是一种字符串匹配算法，由 Daniel M. Sunday 于 1990 年提出。它是对 Boyer-Moore 算法的简化与改进，仅使用一种启发式规则：当发生失配时，考察文本串中当前匹配窗口末尾的下一个字符（即 T[i+m]），并根据该字符在模式串中的最右出现位置决定模式串向右移动的步数。该规则通常能使模式串移动更远，从而在随机文本中获得极高的平均效率。

  • 核心思想：匹配窗口从左向右滑动，但比较顺序通常从左到右（也可从右到左，但典型实现为从左到右）。当失配时，关注窗口之后的下一个字符 c，若 c 在模式串中出现，则将模式串向右移动，使 c 与模式串中该字符最后一次出现的位置对齐；否则，整个窗口跳过 c（即移动 m+1 位）。这种策略使算法在大部分情况下具有接近线性的时间性能。

算法步骤

  1. 预处理：构建一个位移表，记录模式串中每个字符最右边的位置（从 0 开始计数）。

    • 对于模式串 p 中的每个字符 c，记录其最后出现的位置 lastPos[c]（若字符重复，只保留最右侧的索引）。
    • 位移值（移动步数）的计算方法：
      • 当失配时，取文本串中窗口后的字符 next_char = T[i+m]。
      • 若 next_char 在模式串中出现，则移动步数 step = m - lastPos[next_char]。
      • 若未出现，则移动步数 step = m + 1（直接跳过整个窗口及下一个字符）。

  2. 匹配过程：

    • 将模式串与文本串左端对齐，设文本指针 i = 0。
    • 当 i <= n - m 时：
      • 从模式串开头开始逐字符比较 T[i+j] 与 p[j]（j 从 0 到 m-1）。
      • 若完全匹配，返回 i。
      • 若失配，计算 next_char = T[i+m]（注意：当 i+m 超出文本末尾时，直接结束循环）。
      • 根据位移表得到移动步数 step = m - lastPos.get(next_char, -1)，其中 lastPos.get(next_char, -1) 表示字符在模式串中的最右位置（若不存在则为 -1）。
      • 若 next_char 未出现，则 step = m + 1。
      • 将 i 增加 step。
    • 若遍历完未找到，返回 -1。

  3. 结束：返回匹配起始下标或 -1。

内部实现

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
def Sunday(T: str, p: str) -> int:
    n, m = len(T), len(p)
    if m == 0:
        return 0
    # 构建位移表（记录每个字符在模式串中最右出现的位置）
    lastPos = {}
    for i in range(m):
        lastPos[p[i]] = i
    i = 0
    while i <= n - m:
        j = 0
        # 从左到右比较
        while j < m and T[i + j] == p[j]:
            j += 1
        if j == m:
            return i
        # 失配，查看窗口后的下一个字符
        if i + m < n:
            next_char = T[i + m]
            # 移动步数 = m - 该字符在模式串中最右位置（若不存在则为 -1）
            step = m - lastPos.get(next_char, -1)
        else:
            break
        i += step
    return -1

复杂度分析

指标 复杂度 说明
最好时间复杂度 O(m) 首位置即匹配成功
最坏时间复杂度 O(n·m) 例如文本 "aaaa...a"，模式 "ba...a"，每次仅移动 1 位（因为 next_char 始终是 'a'，其最右位置在模式串中可能很近），退化为朴素算法
平均时间复杂度 O(n) 在随机文本中，移动步数通常较大，平均接近线性
空间复杂度 O(σ) 位移表大小取决于字符集大小 σ（如 ASCII 为 256）

说明：

  • 与 Horspool 算法类似，Sunday 算法的最坏情况虽然存在，但实际场景中很少出现。
  • 相比 Horspool，Sunday 使用窗口后的下一个字符，通常能获得更大的跳跃距离，尤其在模式串较短时效果明显。

应用场景

  • 单模式串匹配：适用于文本编辑器中的查找、敏感词过滤、DNA 序列匹配、日志检索等场景。
  • 与 KMP、BM、Horspool 的对比：
    • KMP：最坏情况稳定 O(n+m)，但跳跃小，适合模式串重复较多或需要保证最坏性能的场景。
    • BM：结合坏字符和好后缀，跳跃较大，但实现复杂。
    • Horspool：仅使用坏字符规则，跳跃比 BM 小，但实现简单。
    • Sunday：使用窗口后字符，跳跃通常大于 Horspool，平均性能优异，实现也相对简单。
  • 实际系统应用：许多文本编辑器的快速查找、代码搜索引擎的简单匹配、部分正则引擎的快速预过滤等。

总结

Sunday 算法通过利用匹配窗口之后的下一个字符来决定跳跃步数，在平均情况下具有出色的性能，实现简单且易于理解。尽管最坏情况可能退化，但在大多数实际应用中表现优异，是字符串匹配的实用选择之一。

相关