# BM、比特并行与算法比较

> 来源：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 表示匹配状态活跃：

```text
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：

```text
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 时每字符常数个字操作 |

不要只按复杂度符号认定实际运行速度；预处理、缓存、输出量、字母表和模式分布都影响结果。
