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

题目描述：给定一个表示DNA序列的字符串s，只包含'A','C','G','T'四种字符。找出所有长度为10的子串，这些子串在字符串中出现超过一次。

解题过程：

1. 问题分析
   DNA序列由4种字符组成，我们需要找到所有长度为10的重复子串。例如，对于s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"，长度为10的重复子串有"AAAAACCCCC"和"CCCCCAAAAA"。

2. 暴力解法的问题
   最直接的方法是使用哈希表记录每个长度为10的子串及其出现次数：

• 遍历所有可能的起始位置（0到len(s)-10）
• 截取每个长度为10的子串
• 用哈希表统计每个子串的出现次数
• 最后筛选出出现次数>1的子串

这种方法时间复杂度O(10n)，但当n很大时，截取子串的操作会消耗较多时间和空间。

3. Rabin-Karp滚动哈希的优势
   Rabin-Karp算法通过滚动哈希可以在O(1)时间内计算下一个子串的哈希值，避免重复计算。

4. 哈希函数设计
   由于DNA只有4种字符，我们可以用4进制编码：

• A→0, C→1, G→2, T→3
  这样每个长度为10的子串可以表示为一个4进制的10位数。

例如："ACGT"可以表示为：0×4³ + 1×4² + 2×4¹ + 3×4⁰

5. 滚动哈希计算
   设当前子串s[i...i+9]的哈希值为H(i)，那么下一个子串s[i+1...i+10]的哈希值为：
   H(i+1) = 4 × (H(i) - s[i] × 4⁹) + s[i+10]

其中4⁹是预先计算好的常数。

6. 具体实现步骤

• 预处理：计算4⁹的值
• 计算第一个子串s[0...9]的哈希值
• 初始化哈希表，记录每个哈希值对应的子串起始位置
• 从左到右滑动窗口：
  • 计算当前窗口的哈希值
  • 检查哈希表中是否已存在相同哈希值
  • 如果存在，比较实际子串是否相同（解决哈希冲突）
  • 更新哈希表
• 收集所有重复出现的子串

7. 哈希冲突处理
   由于哈希值可能冲突，我们需要：

• 当发现相同哈希值时，比较实际子串内容
• 可以使用另一个哈希表记录子串内容，或者直接比较字符串

8. 复杂度分析

• 时间复杂度：O(n)，每个子串处理时间为O(1)
• 空间复杂度：O(n)，用于存储哈希映射

这种方法的优势在于避免了重复的字符串操作，通过数学运算快速计算哈希值，特别适合处理长DNA序列。