来源:IDS 课件第 63–83 页。
1. BM 从右向左比较#
BM(Boyer–Moore)在当前窗口中从模式末端向前比较。失配后,利用坏字符和好后缀规则移动整个窗口,通常可以跳过一些起点。
**坏字符规则:**设在模式下标 j 处遇到文本字符 c,找 c 在模式中的合适出现位置,使其对齐;若不存在,可跳过更大距离。
例:P=ABCD,当前窗口最后一位是 X。X 根本不在模式中,可以移动 4 位。若末位是 B,可把模式中的 B 对齐到它,移动 2 位。
**好后缀规则:**若末尾已经匹配了一段 u,则寻找模式中更靠左的合适 u 出现位置;没有则寻找 u 的后缀中能与模式前缀重合的部分。
两种规则给出可行移动量,标准实现结合使用,选择满足正确性的更大位移。
2. BM 的性能不能只背“最快”#
课件给出基本 BM 的最坏情况可为 O(nm),加合适改进可达到线性最坏界。许多实际文本中跳跃会很有效,但性能受文本、模式、字母表和实现影响。
“从右比较”指窗口内比较顺序,不是把整段文本从末尾扫到开头。
3. NFA 与 DFA#
DFA 在一个时刻处于一个确定状态;NFA 的模拟可维护一组同时活跃状态。NFA 不是“随机选一条路”,而是接受性按可能路径定义。
模式匹配可以把每个前缀看成状态。比特并行用一个机器字中的多个 bit 表示多个前缀是否活跃,用一次位运算并行更新。
4. Shift-And#
约定模式从左到右第 i 个字符对应从低到高第 i 位,1 表示匹配状态活跃:
B[c]:模式中等于 c 的位置置 1 D 初始为 0 每读入一个字符 c:D = ((D << 1) | 1) & B[c] 若 D & (1 << (m−1)) 非零,则有模式在当前位置结束 |
左移是延长旧匹配;OR 1 允许从当前字符重新开始;AND B[c] 只保留符合当前字符的状态。
手算 P=aba,T=ababa#
用三位二进制显示,最低位表示匹配了第一个字符 a:B[a]=101,B[b]=010。
| 当前输入 | D(仅保留3位) | 是否完整匹配 |
|---|---|---|
| a | 001 | 否 |
| b | 010 | 否 |
| a | 101 | 是,结束于第3个字符 |
| b | 010 | 否 |
| a | 101 | 是,结束于第5个字符 |
所以起点是 1、3(这里按 1 起始编号)。位向量可以同时记住多个长度的匹配前缀。
5. Shift-Or#
改用 0 表示活跃,掩码中对应字符位置为 0,其他为 1:
D 初始为全 1 D = (D << 1) | B[c] # 在固定有效位宽内处理 最高模式位为 0 表示完整匹配 |
Shift-And/Or 的状态含义相反,初始化、掩码和判定条件必须成套使用。
当 m 不超过机器字长 w 时,单字操作模拟很高效;超出时要跨多个字处理,不能继续假定每字符仅一个普通机器字操作。
6. 通配符与多模式边界#
课件的通配符 * 表示匹配一个任意字符,可把该位置在所有字符掩码中置为可匹配;不要和某些正则/文件匹配语法中的“任意长度”混淆。
AC 的状态转移结构不是一条简单线性链,不能把 AC 节点随便编号后直接套同一个 Shift-And 左移公式。
7. 算法比较#
| 算法 | 场景 | 主要思想 | 本课复杂度要点 |
|---|---|---|---|
| 蛮力 | 单模式、简单实现 | 每位置重新比较 | 最坏 O(nm) |
| MP/KMP | 单模式 | 利用前缀/后缀回退 | O(n+m) |
| AC | 多模式 | Trie+fail+output | 适当假设下 O(n+occ) 搜索 |
| 基本 BM | 单模式 | 从右比较并跳跃 | 课件给出最坏 O(nm),有线性改进 |
| Shift-And/Or | 短模式等 | 位运算模拟状态集合 | m≤w 时每字符常数个字操作 |
不要只按复杂度符号认定实际运行速度;预处理、缓存、输出量、字母表和模式分布都影响结果。