Rabin-Karp 算法在重复DNA序列查找中的应用

题目描述

给定一个表示DNA序列的字符串 s，DNA序列由字母 'A'、'C'、'G'、'T' 组成，长度可能非常大。题目要求找出所有长度为 L（例如 L=10）且在字符串中出现超过一次的子串（即重复出现的DNA序列片段）。返回这些重复子串的列表，顺序任意。
例如，输入 s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", L = 10，输出可能是 ["AAAAACCCCC","CCCCCAAAAA"]。

解题思路

这个问题看似简单，但如果用最直观的方法（枚举所有长度为L的子串，并两两比较）会导致时间复杂度高达 O(nL²)，当 n 很大时（比如 n=10⁶），这是不可接受的。
核心难点：如何在 O(n) 时间内完成查找，避免对每个子串都进行耗时的字符串比较？

这时候，哈希算法就派上用场了。我们可以用 Rabin-Karp 算法 的思想，通过滚动哈希快速计算子串的哈希值，从而在常数时间内比较子串是否相等。
基本步骤：

1. 将 DNA 字符映射为数字（A→0, C→1, G→2, T→3），这样每个长度为 L 的子串可以看作一个 L 位的 4 进制数。
2. 用滚动哈希计算每个子串的哈希值，并存入哈希表（字典）进行计数。
3. 当某个哈希值出现次数等于2时，记录对应的子串（注意要处理哈希冲突）。

详细步骤（循序渐进）

步骤 1：字符到数字的映射

DNA 只有 4 种字符，我们可以将其映射为 0,1,2,3：

• A → 0
• C → 1
• G → 2
• T → 3

这样，一个长度为 L 的子串就可以看作一个 L 位的 4 进制数。
例如，子串 "AAAAACCCCC" 映射为数字序列 0,0,0,0,0,1,1,1,1,1，对应的 4 进制数值为：
0*4^9 + 0*4^8 + ... + 1*4^0。这个数值可以作为哈希值的基础。

步骤 2：滚动哈希的计算

滚动哈希的核心在于，当我们知道前一个子串的哈希值时，可以在 O(1) 时间内计算出下一个子串的哈希值，而不必每次都重新计算整个 L 位数字。

设：

• base = 4（因为 4 进制）。
• h 为当前子串的哈希值（用一个整数表示）。

计算第一个子串的哈希值：
从 s[0] 到 s[L-1]，按以下公式计算：

h = 0
for i in range(L):
    h = h * base + map[s[i]]

这里 map[s[i]] 是字符对应的数字。
相当于在构造一个 L 位的 4 进制数。

滚动到下一个子串：
假设我们已知子串 s[i-L .. i-1] 的哈希值为 h_old，要计算子串 s[i-L+1 .. i] 的哈希值 h_new。
操作如下：

1. 移除最高位（最左边的字符）的影响：h_old = h_old - map[s[i-L]] * (base^(L-1))。
2. 整体左移一位（乘以 base）：h_old = h_old * base。
3. 加上新的最低位（新字符）：h_new = h_old + map[s[i]]。

这样，我们就在 O(1) 时间内得到了新子串的哈希值。

步骤 3：哈希表记录与去重

我们用一个哈希表（字典）来存储每个哈希值出现的次数。
遍历所有长度为 L 的子串：

• 计算当前子串的哈希值（用滚动哈希）。
• 在哈希表中增加该哈希值的计数。
• 如果某个哈希值的计数刚好变成 2，则说明这个子串第一次重复出现，将其加入结果列表（注意存储实际的子串，而不是哈希值）。

关键细节：

• 由于我们只关心哈希值计数为 2 的时刻，所以当计数 >2 时，不再重复添加，避免结果列表中出现重复子串。
• 如果哈希冲突发生（不同子串算出相同哈希值），可能导致误报。解决冲突的方法有两种：
  1. 当哈希值计数为2时，不直接记录子串，而是存储这个哈希值对应的所有子串起始位置，然后进一步验证这些子串是否真的相等（字符串比较）。
  2. 使用“双哈希”或“多哈希”，即用两个不同的 base 和模数计算两个哈希值，当两个哈希值都相等时才认为子串相等。这可以极大降低冲突概率，在大多数情况下可以避免验证。

步骤 4：处理整数溢出

当 L 较大时，4^L 会非常大，可能超出整数范围。通常的解决方案是取一个模数（大质数），比如 mod = 10**9+7 或 2**32（利用自然溢出）。
在滚动计算中，乘法和减法都要在模运算下进行，确保结果一致。

滚动公式（带模数）：
设 base_pow = base^(L-1) % mod 预先计算好。
则：

h_new = ((h_old - map[s[i-L]] * base_pow) * base + map[s[i]]) % mod

注意：减法的结果可能为负，需要加 mod 再取模。

步骤 5：算法复杂度

• 时间复杂度：O(n)，因为每个字符访问常数次（计算哈希、更新哈希表）。
• 空间复杂度：O(n)，哈希表最多存储 n-L+1 个子串的哈希值。

示例演示

以 s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", L=10 为例：

1. 映射：A=0, C=1, G=2, T=3。
2. 计算第一个子串 "AAAAACCCCC" 哈希值 h0。
3. 滚动到下一个子串 "AAAACCCCCA" 哈希值 h1，依此类推。
4. 哈希表记录每个哈希值出现次数。当 "AAAAACCCCC" 再次出现时，其哈希值计数变为2，将其加入结果。同样处理 "CCCCCAAAAA"。

关键点总结

• 滚动哈希是 Rabin-Karp 算法的核心，它让子串哈希值的计算在 O(1) 时间内完成。
• 通过哈希表记录出现次数，可以在线性时间内找出重复子串。
• 注意处理哈希冲突（可通过验证或双哈希解决）和整数溢出（取模）。
• 此方法不仅适用于 DNA 序列，也适用于任何在长文本中查找固定长度重复模式的问题。

通过以上步骤，我们就可以高效地解决“查找重复DNA序列”这一经典问题了。