Function horspool

codes/python/04_string/string_horspool.py:2–15

(T: str, p: str)

# horspool 算法，T 为文本串，p 为模式串
def horspool(T: str, p: str) -> int:
    n, m = len(T), len(p)
    
    bc_table = generateBadCharTable(p)          # 生成后移位数表
    
    i = 0
    while i <= n - m:
        j = m - 1
        while j > -1 and T[i + j] == p[j]:      # 进行后缀匹配，跳出循环说明出现坏字符
            j -= 1
        if j < 0:
            return i                            # 匹配完成，返回模式串 p 在文本串 T 中的位置
        i += bc_table.get(T[i + m - 1], m)      # 通过后移位数表，向右进行进行快速移动
    return -1                                   # 匹配失败

# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离