字符串匹配的Sunday算法

1. 问题描述
Sunday算法是一种用于字符串匹配的高效算法，其目标是在主串（文本）中快速查找子串（模式）的出现位置。与KMP算法从前往后匹配不同，Sunday算法利用匹配失败时文本中当前窗口下一个字符的位置信息，尽可能大地跳过不必要的比较，平均时间复杂度接近O(n)，最坏情况下为O(nm)（n为主串长度，m为模式串长度）。

2. 核心思想
Sunday算法的核心是坏字符规则（与Boyer-Moore算法类似，但更简单）：

• 匹配过程中，当发现模式串与文本当前窗口不匹配时，检查文本中当前窗口末尾的下一个字符（即参与匹配的文本区间后的第一个字符）。
• 根据该字符在模式串中的出现位置，决定模式串向右移动的步长，从而跳过尽可能多的字符。

3. 预处理：建立偏移表（Shift Table）
在匹配前，需要预处理模式串，生成一个偏移表（哈希表结构），记录每个字符在模式串中最后一次出现的位置到模式串末尾的距离。具体规则：

• 对于模式串中的每个字符，偏移值 = 模式串长度 - 该字符在模式串中最后一次出现的下标。
• 若字符不在模式串中，偏移值 = 模式串长度 + 1（即直接跳过整个窗口）。

示例：
模式串 "example"，长度 m=7：

• 字符 'e' 最后出现在下标6（从0开始），偏移值 = 7 - 6 = 1。
• 字符 'x' 最后出现在下标1，偏移值 = 7 - 1 = 6。
• 字符 'z' 不在模式串中，偏移值 = 7 + 1 = 8。

4. 匹配过程详解
假设文本为 "this is an example"，模式串为 "example"，偏移表已预计算。

1. 初始对齐：
   文本窗口从下标0开始，窗口长度与模式串相同（7个字符）。
   窗口文本："this is"，与 "example" 比较，第一个字符 't' 与 'e' 不匹配。

2. 检查下一个字符：
   当前窗口末尾的下一个字符是文本下标7的字符 ' '（空格）。
   查偏移表：' ' 不在模式串中，偏移值 = 8。
   将模式串向右移动8位，新窗口起始位置 = 0 + 8 = 8。

3. 继续匹配：
   新窗口文本："is an e"，与 "example" 比较，首字符 'i' 与 'e' 不匹配。
   下一个字符是文本下标15的字符 'x'。
   查偏移表：'x' 的偏移值 = 6。
   模式串右移6位，新窗口起始位置 = 8 + 6 = 14。

4. 匹配成功：
   窗口文本："example"，与模式串完全匹配，记录位置14。
   继续移动（偏移值1）以查找下一个匹配。

5. 算法模板（伪代码）

1. 预处理模式串生成偏移表shift_table：
   for i in range(0, len(pattern)):
       shift_table[pattern[i]] = len(pattern) - i   # 重复字符会被覆盖为最后出现的位置
   对于未出现的字符，偏移值默认为len(pattern) + 1

2. 文本指针i初始化为0，循环直到i + len(pattern) > len(text)：
   a. 从位置i开始，比较文本与模式串的每个字符：
      - 若全部匹配，记录位置i。
   b. 设next_char = text[i + len(pattern)]（若越界则终止）。
   c. 根据shift_table[next_char]计算移动步长，i += shift_table[next_char]。

6. 关键点与性能分析

• 优势：实现简单，在常见场景下（如英文文本）比KMP和Boyer-Moore更快。
• 劣势：最坏情况下（如文本"aaaaaaa"匹配模式"aaaab"）退化为O(nm)。
• 优化：可与KMP的“好前缀”规则结合，避免最坏情况。

7. 应用场景
适合短模式串、字符集较大的场景（如IDE中的查找、日志过滤工具），因其跳跃能力比暴力匹配显著提升。