波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

在长文本里找一段文字：蛮力法逐位硬比（O(n x m)，慢但好懂）；BM 算法（Boyer-Moore）反着比，撞上坏字符就按表大步跳跃——一次能跳过一整段，越不匹配跳得越远；你每天调的 find／Ctrl+F，底层就是这一族的智慧。

📝 本节和前面几节的关系

4-15 查的是【数组里的一个数】，这一篇升级到【一整段子串】。回收 3-9 的字符串（字符可当数字比）与 4-14 的复杂度账（O(n x m) 对 O(n)）。

一、蛮力法：逐位硬比

对齐模式串，一个字符一个字符比；失配就整体右移一位、从头再比：

def brute_force(text, pat):
    n, m = len(text), len(pat)
    for i in range(n - m + 1):          # 每个可能的起点
        if text[i:i + m] == pat:        # 从该起点整段比
            return i
    return -1

print(brute_force("ABABCABABCD", "ABCD"))    # 7

性格：O(n x m)——文本长 1 亿、模式 10 字符，最坏十亿次比较；简单到不会写错，小数据够用，是所有高级算法的对照组。

二、BM 算法：反着比、跳着走

Boyer-Moore（1977）两大反直觉设计：

  1. 从右往左比：模式串末尾字符先对齐比较——而人的直觉是从左往右；
  2. 坏字符跳跃：比对时撞上【文本里这个字符】在模式串对应位置之外根本没有——模式串可以大步跳过去，对齐到该字符最后出现的位置：
文本   A B A B C A B A B C D ...
模式   A B C D                末尾比：模式 C 对文本 C？模式[3] D 与文本[3] C 失配
                              -> 按 B（坏字符）在模式里的位置，右移 2 格

失配得越彻底跳得越远——最好情况 O(n/m)（比 n 还快），最坏 O(n x m)；日常文本远好于蛮力。它在文本编辑器搜索、grep 家族里服役至今。

def bm_bad_char(text, pat):
    # 坏字符表：每个字符在模式串中最后出现的位置
    last = {ch: k for k, ch in enumerate(pat)}
    n, m = len(text), len(pat)
    i = 0
    while i <= n - m:
        j = m - 1                       # 从模式串末尾开始比
        while j >= 0 and text[i + j] == pat[j]:
            j -= 1
        if j < 0:
            return i                    # 全匹配
        shift = j - last.get(text[i + j], -1)   # 坏字符跳跃步数（至少 1）
        i += max(shift, 1)
    return -1

print(bm_bad_char("ABABCABABCD", "ABCD"))    # 7

读结果：与蛮力同答案（下标 2），路径不同——失配时按坏字符表跳，而不是挪一格。

三、BM 的同伴与后来者

四、动手 Demo：跳步可视化

text = "ABABCABABCD"
pat = "ABCD"

def bm_verbose(text, pat):
    last = {ch: k for k, ch in enumerate(pat)}
    i, hop = 0, 0
    while i <= len(text) - len(pat):
        j = len(pat) - 1
        while j >= 0 and text[i + j] == pat[j]:
            j -= 1
        if j < 0:
            print(f"命中于起点 {i}，共跳了 {hop} 次")
            return i
        s = max(j - last.get(text[i + j], -1), 1)
        print(f"起点 {i}：失配于模式[{j}]，跳 {s} 格")
        i += s; hop += 1
    return -1

bm_verbose(text, pat)

看到什么算成功（沙箱实跑输出）：

起点 0：失配于模式[3]，跳 2 格
起点 2：失配于模式[3]，跳 3 格
起点 5：失配于模式[3]，跳 2 格
命中于起点 7，共跳了 3 次

读结果：命中只用了 4 次对齐、跳 3 次（蛮力要试 8 个起点、逐位可比）——跳跃让检查的起点数大幅缩水，这就是 BM 的全部魔法。

五、30 秒实验

跑 print("ABABCABABCD".find("ABCD"))——得 7。Python 的 find 一行顶上面三十行（底层是高效混合实现）；再跑 find 找不存在的子串——返回 -1 而不是抛异常——查不到是正常情况，不是错误（对照 4-8 的异常哲学）。

六、常见误区

  1. 【BM 从右往左比是个怪癖，没实质意义】——错。这是它跳跃能力的来源：末尾先失配才能【按坏字符表整段跳】；从左往右撞上第一个字符就卡死，跳不动。
  2. 【字符串查找要自己实现】——不用。str.find／in／正则都是高度优化的成品；学 BM 是为了读懂复杂度与面试，实战写 pat in text 即可。
  3. 【find 找不到会报错】——错。返回 -1（正常信号）；真正会抛异常的是 str.index——两个方法一字之差、失败行为不同，用错就是线上事故。
自测三问（点开对答案） 1. **蛮力法字符串查找的复杂度与问题？** 答：O(n x m)——每个起点整段硬比；简单可靠但大数据下比较次数爆炸。 2. **BM 算法的两大设计及其收益？** 答：从右往左比对＋坏字符表跳跃——失配时一次跳过一整段，平均接近 O(n/m)，比蛮力少验大半起点。 3. **str.find 与 str.index 的区别？** 答：找不到时 find 返回 -1（正常信号）、index 抛 ValueError——按业务选：查不到属正常用 find，查不到算异常用 index 配 try。

相关笔记