4.8 Sunday 算法

[giscus[bot]]

4.8 Sunday 算法

Sunday 算法 1. Sunday 算法介绍 「Sunday 算法」 是一种在字符串中查找子串的算法，是 Daniel M.Sunday 于1990年提出的字符串模式匹配算法。 Sunday 算法思想：对于给定文本串 T 与模式串 p，先对模式串 p 进行预处理。然后在匹配的过程中，当发现文本串 T 的某个字符与模式串 p 不匹配的时候，根据启发策...

https://algo.itcharge.cn/04_string/04_08_string_sunday/

[eddieai]

代码部分可以略微改进一下：

def sunday(text: str, pattern: str) -> int:
n, m = len(text), len(pattern)

# 生成坏字符表
bad_char_table = {char: m - i for i, char in enumerate(pattern)}

i = 0
while i <= n - m:
    # 逐字符比较，替代切片操作
    if text[i: i+m] == p:
        return i
    
    if i + m >= n:
        return -1  # 已到文本串末尾，未找到匹配
    
    # 计算移动距离
    move = bad_char_table.get(text[i + m], m + 1)
    i += move  # 向右移动

return -1  # 未找到匹配