Sunday算法详解（Python语言实现高效字符串匹配）

算法步骤解析

1. 对模式串（要查找的字符串）建立一个“偏移表”，记录每个字符在模式串中最右边出现的位置到末尾的距离。
2. 将模式串与主串对齐，从左到右逐字符比较。
3. 如果全部匹配成功，返回起始位置；否则，查看主串中“当前窗口后一个字符”（即 pattern 长度 + 当前起始位置 的字符）。
4. 根据偏移表，决定下一次对齐的位置：若该字符不在模式串中，则跳过整个模式串长度+1；否则，按偏移表跳转。

Python实现Sunday算法

下面是一个完整的、可运行的Python代码实现：

def sunday_search(text, pattern):    """    使用Sunday算法在text中查找pattern    返回第一次匹配的起始索引，未找到返回-1    """    if not pattern:        return 0    if len(pattern) > len(text):        return -1    # 构建偏移表    shift_table = {}    pattern_len = len(pattern)    for i in range(pattern_len):        # 记录每个字符最右边出现的位置到末尾的距离        shift_table[pattern[i]] = pattern_len - i    i = 0  # 主串中的起始位置    while i <= len(text) - pattern_len:        # 检查当前窗口是否匹配        match = True        for j in range(pattern_len):            if text[i + j] != pattern[j]:                match = False                break        if match:            return i  # 找到匹配        # 查看主串中“窗口后一个字符”        next_char_index = i + pattern_len        if next_char_index >= len(text):            break        next_char = text[next_char_index]        # 根据偏移表决定跳转距离        if next_char in shift_table:            i += shift_table[next_char]        else:            i += pattern_len + 1    return -1  # 未找到# 测试示例if __name__ == "__main__":    text = "Hello, welcome to the world of Sunday algorithm!"    pattern = "Sunday"    index = sunday_search(text, pattern)    print(f"Pattern found at index: {index}")  # 输出: Pattern found at index: 28

代码说明

• shift_table 是偏移表，例如对于模式串 "abcab"，字符 'a' 的偏移值是 5 - 3 = 2（因为最右边的 'a' 在索引3）。
• 主循环中，每次匹配失败后，我们查看 text[i + len(pattern)] 这个字符。
• 如果该字符不在模式串中，直接跳过 len(pattern) + 1 位，避免无效比较。

为什么选择Sunday算法？

相比其他字符串匹配算法，Sunday算法具有以下优势：

• 实现简单，逻辑清晰，适合初学者理解。
• 平均时间复杂度接近 O(n/m)，其中 n 是主串长度，m 是模式串长度。
• 在实际文本搜索中（如日志分析、关键词提取），性能往往优于KMP。

总结

通过本教程，你已经学会了如何用Python语言实现Sunday算法进行高效字符串搜索。无论你是准备面试，还是开发文本处理工具，掌握这一算法都将大有裨益。记住，Sunday算法的关键在于“聪明地跳过不可能匹配的位置”，从而减少比较次数。

赶快动手试试吧！修改上面的代码，在自己的项目中应用这个强大的字符串匹配技术。