4. OldR vs R

这四种操作的区别，本质上来源于在动态规划（DP）视角下，当前状态是从哪个相邻状态转移过来的。

在 Bitap 算法中，两个关键变量决定了公式怎么写：

1. oldR vs R：决定文本指针是否移动。
   • oldR 代表上一个文本位置（因为算法是从文本末尾向前遍历，oldR 是文本位置 $i+1$ 的状态）。使用 oldR 意味着消耗了一个文本字符。
   • R 代表当前文本位置（文本位置 $i$ 的状态）。使用 R 意味着没有消耗文本字符（文本指针停在原地）。
2. << 1（左移一位）：决定模式指针是否移动。
   • 有 << 1 意味着消耗了一个模式字符（模式指针向右滑动一格）。
   • 没有 << 1 意味着没有消耗模式字符（模式指针不动）。
3. d-1 vs d：决定错误数是否增加。
   • 从 d-1 转移到 d，意味着引入了一个新的错误。
   • 保持 d 不变，意味着没有引入新错误（匹配）。

我们逐一拆解这四种情况：

---

1. 删除 (Deletion, D)

• 生物学/字符串含义：文本多了一个字符（或模式缺失了这个字符）。我们需要跳过这个文本字符，模式指针不动。
• 文本指针：需要前进（跳过文本字符）→ 必须用 oldR（消耗文本）。
• 模式指针：不动（模式没有字符去匹配）→ 无 << 1。
• 错误数：发生了删除错误 → 从 d-1 转移过来。
• 公式：D = oldR[d-1]
• 解读：上一个文本位置已经允许 $d-1$ 个错误，当前文本字符直接跳过（不消耗模式），构成删除。

2. 替换 (Substitution, S)

• 生物学/字符串含义：文本和模式都有字符，但两者不匹配。需要同时跳过这两个字符。
• 文本指针：需要前进（跳过不匹配的文本字符）→ 必须用 oldR（消耗文本）。
• 模式指针：前进（跳过不匹配的模式字符）→ 有 << 1。
• 错误数：发生了替换错误 → 从 d-1 转移过来。
• 公式：S = (oldR[d-1] << 1)
• 解读：上一个文本位置允许 $d-1$ 个错误，当前文本字符和模式字符同时消耗掉，构成替换。

3. 插入 (Insertion, I)

• 生物学/字符串含义：模式多了一个字符（或文本缺失了这个字符）。我们需要跳过这个模式字符，文本指针不动。
• 文本指针：不动（文本没有字符去匹配）→ 必须用 R（不消耗文本）。
• 模式指针：前进（跳过模式字符）→ 有 << 1。
• 错误数：发生了插入错误 → 从 d-1 转移过来。
• 公式：I = (R[d-1] << 1)
• 解读：在当前文本位置允许 $d-1$ 个错误，直接消耗一个模式字符，构成插入。注意这里用的是 R，因为当前文本字符并没有被消耗，它还要留着给后面的状态用。

4. 匹配 (Match, M)

• 生物学/字符串含义：文本和模式字符完全匹配。同时跳过这两个字符，错误数不变。
• 文本指针：需要前进 → 必须用 oldR（消耗文本）。
• 模式指针：前进 → 有 << 1。
• 错误数：无错误，保持 $d$ → 用 oldR[d]（注意这里是 $d$，不是 $d-1$）。
• 公式：M = (oldR[d] << 1) | curPM
• 解读：上一个文本位置已经允许 $d$ 个错误，当前文本字符和模式字符同时消耗，并且通过 | curPM 检查它们是否匹配。

---

总结对比

操作	文本指针（决定用 oldR 还是 R）	模式指针（决定是否有 << 1）	错误数（决定 $d$ 还是 $d-1$）	公式
删除 (D)	移动 (oldR)	不动 (无 <<1)	增加 (d-1)	oldR[d-1]
替换 (S)	移动 (oldR)	移动 (<<1)	增加 (d-1)	(oldR[d-1] << 1)
插入 (I)	不动 (R)	移动 (<<1)	增加 (d-1)	(R[d-1] << 1)
匹配 (M)	移动 (oldR)	移动 (<<1)	不变 (d)	(oldR[d] << 1) | curPM

核心记忆点：

• 用了 R 而不是 oldR，意味着“不消耗文本字符”（只有插入操作是这样，因为文本指针要停在原地）。
• 用了 oldR 而不是 R，意味着“消耗了文本字符”（删除、替换、匹配都会消耗文本字符）。
• << 1 则代表“消耗了模式字符”（删除操作不消耗模式，所以没有左移）。

这正好对应了动态规划矩阵中，计算当前格子 (i, j) 时，是从左边 (i, j-1) 还是上边 (i-1, j) 转移过来的逻辑。因为在 Bitap 中文本是反向遍历的，所以对应关系是：oldR 对应上一行（文本 i+1），R 对应当前行（文本 i）。