Horspool 算法

基本概念

Horspool 算法是 Boyer-Moore 算法的一种简化版本，由 Nigel Horspool 于 1980 年提出。它仅使用 Boyer-Moore 算法中的“坏字符规则”，舍弃了“好后缀规则”，因此实现更简单，但在大多数实际场景中依然具有较高的效率。

核心思想：将模式串与文本串从左到右对齐，但从右向左进行字符比较。当发生不匹配时，根据文本串中当前对齐位置的字符（即造成失配的字符）在模式串中最右出现的位置，决定模式串向右移动的步数。这种跳跃策略能够跳过大量不可能匹配的位置，从而提升匹配速度。

算法步骤

预处理：构建一个位移表（也称坏字符表），记录模式串中每个字符在失配时应该移动的步数。
- 对于模式串 p 的长度 m，除最后一个字符外，每个字符 c 的位移值为 m - 1 - i，其中 i 是该字符在模式串中最后一次出现的位置（从 0 开始计数）。
- 对于不在模式串中的字符，位移值设为 m。
- 注意：若一个字符出现多次，只保留最右侧出现的位置。
匹配过程：
- 将模式串与文本串左端对齐，设文本指针 i = m - 1（指向文本串中与模式串最后一个字符对齐的位置）。
- 重复以下步骤直到 i >= n（文本长度）：
  - 从模式串末尾开始向左比较：k = m - 1，同时比较 T[i - (m-1 - k)] 与 p[k]。
  - 若完全匹配（k < 0），则返回匹配起始下标 i - m + 1。
  - 若不匹配，则根据失配字符 T[i] 查找位移表，得到移动步数 step = move.get(T[i], m)，将 i 增加 step。
结束：若遍历完文本未找到匹配，返回 -1。

内部实现：

def Horspool(T: str, p: str) -> int:
    n, m = len(T), len(p)
    if m == 0:
        return 0
    # 构建位移表
    move = {}
    for i in range(m - 1):
        move[p[i]] = m - 1 - i   # 字符在模式串中最右出现位置（除末尾）对应的步数
    i = m - 1
    while i < n:
        k = m - 1
        # 从右向左比较
        while k >= 0 and T[i - (m - 1 - k)] == p[k]:
            k -= 1
        if k < 0:                # 完全匹配
            return i - m + 1
        else:                    # 发生失配，根据 T[i] 移动
            i += move.get(T[i], m)
    return -1

复杂度分析：

指标	复杂度	说明
最好时间复杂度	O(m)	模式串首次对齐即匹配成功，仅需 O(m) 次比较
最坏时间复杂度	O(n·m)	例如文本 `"aaaa...a"`，模式 `"ba...a"`，每次失配仅移动 1 步，退化为朴素算法
平均时间复杂度	O(n)	在随机文本中，跳跃步数较大，平均接近线性
空间复杂度	O(σ)	位移表大小取决于字符集大小 σ（如 ASCII 为 256）

说明：

位移表的大小与字符集相关，对于小字符集（如 DNA 序列、英文小写）非常轻量。
最坏情况虽然存在，但实际应用中很少出现，整体性能优于朴素算法。

应用场景

单模式串匹配：适用于模式串长度较短、字符集规模较小的场景，如文本编辑器中的查找、关键字过滤、DNA 序列匹配等。
与 KMP、BM 的对比：
- KMP：利用前缀信息，匹配过程稳定 O(n+m)，但预处理 O(m) 且跳跃较小。
- BM：结合坏字符和好后缀，最坏情况仍为 O(n+m)，实际跳跃更大，但实现复杂。
- Horspool：仅用坏字符规则，实现简单，平均性能接近 BM，适合工程快速实现。
实际系统应用：许多文本编辑器的查找功能（如 Notepad++、VS Code）在简单搜索时可能会采用类似策略；某些正则引擎在纯文本匹配时也会使用。

总结

Horspool 算法是 Boyer-Moore 算法的一个轻量级版本，通过预处理位移表实现跳跃式匹配，平均效率高且实现简单。尽管最坏情况可能退化为 O(n·m)，但在实际应用中表现优异，尤其适合短模式串和中等规模文本的快速匹配场景。