高效字符串匹配利器：Sunday算法详解（Python语言Sunday算法实现与实战）

Sunday算法的核心思想

假设我们有一个主串 text 和一个模式串 pattern。算法从左到右对齐模式串与主串进行比较：

1. 如果所有字符都匹配，则找到一个匹配位置；
2. 如果在某个位置发生不匹配，查看主串中当前对齐窗口下一个字符（即 text[i + len(pattern)]）；
3. 根据这个“坏字符”，查表确定模式串应向右移动多少位，使得该字符尽可能与模式串中的最右出现位置对齐；
4. 重复上述过程，直到遍历完主串。

构建偏移表（Shift Table）

为了快速决定移动距离，我们需要预先为模式串构建一个偏移表。该表记录了模式串中每个字符到其最右端的距离（从1开始计数）。如果某字符不在模式串中，则偏移量为 len(pattern) + 1。

例如，模式串 "ABCD" 的偏移表为：

• A → 4
• B → 3
• C → 2
• D → 1
• 其他字符 → 5

Python实现Sunday算法

下面，我们用Python语言一步步实现Sunday算法。代码清晰易懂，适合编程初学者。

def build_shift_table(pattern):    """    构建Sunday算法的偏移表    :param pattern: 模式串    :return: 偏移字典    """    table = {}    length = len(pattern)    for i in range(length):        # 记录每个字符到最右端的距离（从1开始）        table[pattern[i]] = length - i    return tabledef sunday_search(text, pattern):    """    使用Sunday算法在text中查找pattern    :param text: 主串    :param pattern: 模式串    :return: 所有匹配的起始索引列表    """    if not pattern or not text:        return []        n = len(text)    m = len(pattern)        # 构建偏移表    shift_table = build_shift_table(pattern)        matches = []    i = 0  # 主串中的当前起始位置        while i <= n - m:        # 尝试匹配        j = 0        while j < m and text[i + j] == pattern[j]:            j += 1                if j == m:            # 完全匹配            matches.append(i)            # 移动：查看下一个字符            next_char_index = i + m            if next_char_index < n:                shift = shift_table.get(text[next_char_index], m + 1)            else:                break  # 已到末尾            i += shift        else:            # 不匹配，查看窗口后一个字符            next_char_index = i + m            if next_char_index < n:                shift = shift_table.get(text[next_char_index], m + 1)            else:                break            i += shift        return matches# 测试示例if __name__ == "__main__":    text = "HERE IS A SIMPLE EXAMPLE"    pattern = "EXAMPLE"    result = sunday_search(text, pattern)    print(f"匹配位置: {result}")  # 输出: [17]

代码解析

1. build_shift_table 函数遍历模式串，为每个字符计算其到末尾的距离。

2. sunday_search 函数是主逻辑：

• 首先检查边界条件；
• 然后循环尝试匹配；
• 匹配成功则记录位置，并根据窗口后一个字符决定下一步跳转；
• 匹配失败也根据后一个字符跳转，避免无效比较。

算法复杂度

- 时间复杂度：平均情况为 O(n)，最坏情况为 O(n×m)，但在实际文本中表现优异；

- 空间复杂度：O(k)，其中 k 是字符集大小（用于存储偏移表）。

总结

通过本文，我们学习了Sunday算法的基本原理，并用Python语言实现了完整的字符串匹配功能。这种算法不仅效率高，而且代码简洁，非常适合用于实际项目中的文本搜索任务。

无论你是算法初学者，还是希望优化现有系统的开发者，掌握Sunday算法都将为你提供一个强大而实用的工具。赶快动手试试吧！

SEO关键词提示：本文涵盖关键词包括 Sunday算法、字符串匹配、Python实现、文本搜索。