字符串匹配的Sunday算法
描述
Sunday算法是一种高效的字符串匹配算法，用于在文本串（Text）中查找模式串（Pattern）的出现位置。它由Daniel M. Sunday于1990年提出。与KMP和Boyer-Moore算法相比，Sunday算法的思想更为简单直观，并且在实践中，尤其是在模式串较短或字符集较大时，常常表现出优异的性能。其核心思想是利用匹配失败时文本串中参与匹配的最末字符的下一个字符（我们称之为“黄金字符”）来提供尽可能大的“坏字符”跳跃距离，从而跳过不必要的比较。
解题过程循序渐进讲解
-
基本思想与预备知识
- 目标：在文本串
T(长度为n) 中，找到模式串P(长度为m) 的所有出现位置。通常m <= n。 - 关键洞察：Sunday算法是一种“从前往后”匹配，但“从后往前”检查的算法。当发生匹配失败时，它不像KMP那样利用已匹配部分的信息，而是关注文本串中紧接着当前匹配窗口后的那个字符。
- 匹配窗口：算法将模式串
P与文本串T的一个等长子串进行比较。这个子串的起始索引为i，我们称这个区间T[i : i+m]为当前的匹配窗口。 - 黄金字符：当窗口
T[i : i+m]与P匹配失败时，文本串中索引为i + m的字符（即紧邻当前匹配窗口之后的那个字符）被称为“黄金字符”。如果i + m >= n，说明文本串剩余部分长度已不足以容纳模式串，匹配结束。
- 目标：在文本串
-
偏移表（Shift Table / Sunday Table）的构建
- 为了快速决定匹配失败时模式串应该向右移动多少位，我们需要预先计算一个“偏移表”。
- 规则：对于模式串
P中的每一个字符c：- 如果
c出现在P中，则shift[c] = m - max{ j | P[j] == c, 0 <= j < m }。也就是m减去字符c在P中最后一次出现的位置（从0开始计）。 - 如果
c没有出现在P中，则shift[c] = m + 1。
- 如果
- 通俗解释：这个表记录了，当匹配失败时，如果“黄金字符”是
c，为了让这个“黄金字符”与模式串中某个可能的相同字符对齐（或者因为模式串中不存在该字符而直接跳过整个窗口），模式串需要向右移动的位数。 - 举例：模式串
P = "abacb"，m = 5。- 字符
'a'最后一次出现在位置 2，shift['a'] = 5 - 2 = 3。 - 字符
'b'最后一次出现在位置 4，shift['b'] = 5 - 4 = 1。 - 字符
'c'最后一次出现在位置 3，shift['c'] = 5 - 3 = 2。 - 对于所有其他字符（如
'd','x'等），shift[other] = 5 + 1 = 6。
- 字符
-
匹配过程（算法核心步骤）
- 初始化：令文本串指针
i = 0，即第一个匹配窗口从T[0]开始。 - 尝试匹配：比较
T[i : i+m]和P[0 : m]。- 如果完全匹配，则记录位置
i。
- 如果完全匹配，则记录位置
- 确定跳跃距离：
- 无论上一步是否匹配成功（成功也要继续往后找），都要检查“黄金字符”
T[i + m]。- 如果
i + m >= n，算法结束。
- 如果
- 根据“黄金字符”
c = T[i + m]，查找预先生成的偏移表shift[c]。
- 无论上一步是否匹配成功（成功也要继续往后找），都要检查“黄金字符”
- 移动窗口：将匹配窗口向右移动
shift[c]位。即i = i + shift[c]。 - 重复：回到步骤2，直到
i + m > n，算法结束。
- 初始化：令文本串指针
-
完整示例
-
文本串 T:
"Here is a simple example" -
模式串 P:
"example" -
构建偏移表：
P = "example",m = 6。'e': 最后出现于位置 5? 不，位置 0 (e), 位置 6? 索引从0开始，P[0]='e',P[4]='e'，最后一次在位置4。shift['e'] = 6 - 4 = 2。'x': 位置1，shift['x'] = 6 - 1 = 5。'a': 位置2，shift['a'] = 6 - 2 = 4。'm': 位置3，shift['m'] = 6 - 3 = 3。'p': 位置4，shift['p'] = 6 - 4 = 2。'l': 位置5，shift['l'] = 6 - 5 = 1。- 其他字符：
shift[other] = 7。
-
匹配过程：
-
窗口1 (
i=0): 比较T[0:6] = "Here i"与"example"。第一个字符'H'vs'e'就失败。- 黄金字符：
T[0+6] = T[6] = 's'。 's'不在P中，shift['s'] = 7。- 移动：
i = 0 + 7 = 7。
- 黄金字符：
-
窗口2 (
i=7): 比较T[7:13] = "s a si"与"example"。's'vs'e'失败。- 黄金字符：
T[7+6] = T[13] = 'm'。 shift['m'] = 3。- 移动：
i = 7 + 3 = 10。
- 黄金字符：
-
窗口3 (
i=10): 比较T[10:16] = "a sim"与"example"。'a'vs'e'失败。- 黄金字符：
T[10+6] = T[16] = 'p'。 shift['p'] = 2。- 移动：
i = 10 + 2 = 12。
- 黄金字符：
-
窗口4 (
i=12): 比较T[12:18] = "simpl"与"example"。's'vs'e'失败。- 黄金字符：
T[12+6] = T[18] = 'e'。 shift['e'] = 2。- 移动：
i = 12 + 2 = 14。
- 黄金字符：
-
窗口5 (
i=14): 比较T[14:20] = "mple e"? 等等，T[14]是'm'，T[14:20]应该是"mple ex"的前6个字符"mple e"，与"example"不匹配。仔细看文本串"Here is a simple example"，索引14是's'后面的空格吗？我们需要精确的索引。假设索引如下：
H e r e i s a s i m p l e e x a m p l e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
P = "e x a m p l e"(长度7？我前面误写成6了，应为7)。修正：m = 7。
重新计算偏移表 (m=7)：
'e': 最后在位置6 (e),shift['e'] = 7 - 6 = 1。
'x': 位置1,shift['x'] = 7 - 1 = 6。
'a': 位置2,shift['a'] = 7 - 2 = 5。
'm': 位置3,shift['m'] = 7 - 3 = 4。
'p': 位置4,shift['p'] = 7 - 4 = 3。
'l': 位置5,shift['l'] = 7 - 5 = 2。
其他字符：shift[other] = 8。 -
窗口1 (
i=0):T[0:7]="Here is"vs"example"失败。- 黄金字符：
T[7] = ' '(空格)。shift[' '] = 8。 i = 0 + 8 = 8。
- 黄金字符：
-
窗口2 (
i=8):T[8:15]="a simple"?T[8]='a'vs'e'失败。- 黄金字符：
T[8+7]=T[15]='e'。 shift['e'] = 1。i = 8 + 1 = 9。
- 黄金字符：
-
窗口3 (
i=9):T[9:16]=" simpl"?T[9]=' 'vs'e'失败。- 黄金字符：
T[16]='p'。 shift['p'] = 3。i = 9 + 3 = 12。
- 黄金字符：
-
窗口4 (
i=12):T[12:19]="mple ex"?T[12]='m'vs'e'失败。- 黄金字符：
T[19]='a'。 shift['a'] = 5。i = 12 + 5 = 17。
- 黄金字符：
-
窗口5 (
i=17):T[17:24]="example"。与P完全匹配！记录位置17。- 黄金字符：
T[17+7]=T[24]已超出字符串范围（假设字符串长度为23，索引22是最后一个字符'e'），算法结束。
- 黄金字符：
-
最终找到模式串
"example"在文本串中起始于索引17的位置。 -
-
算法性能分析
- 时间复杂度：
- 最坏情况：O(m * n)。例如，当
T = "aaaaaaaa"，P = "aaaab"时，每次匹配都几乎要比较整个模式串，且跳跃距离很小。 - 平均情况：O(n)。在实际情况和随机数据下，Sunday算法通常能实现亚线性时间，跳跃幅度大，比较次数少。
- 最坏情况：O(m * n)。例如，当
- 空间复杂度：O(|Σ|)，其中 |Σ| 是字符集的大小。主要用于存储偏移表。
- 时间复杂度：
总结
Sunday算法以其简洁的思想和优秀的平均性能著称。它通过关注匹配窗口后的“黄金字符”，利用预计算的偏移表实现大幅跳跃，有效减少了不必要的字符比较。虽然存在理论上的最坏情况，但在实际应用中，特别是在处理自然语言、代码等场景时，它往往比KMP等算法更快、更易于实现。理解Sunday算法的关键在于掌握偏移表的构建规则和基于“黄金字符”进行跳跃的核心逻辑。