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

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

解题过程：

1. 问题分析：

   • DNA序列由4种字符组成，长度为10的子串可能有4^10 = 1,048,576种可能
   • 直接暴力枚举所有子串并比较，时间复杂度为O(10n^2)，对于长序列效率很低
   • 需要一种高效的方法来检测重复出现的固定长度子串

2. Rabin-Karp算法原理：

   • 使用滚动哈希技术，通过哈希值快速比较子串
   • 当两个子串的哈希值相同时，再验证实际内容是否真的相同（防止哈希冲突）
   • 核心思想：通过前一个子串的哈希值快速计算下一个子串的哈希值

3. 哈希函数设计：

   • 将4个字符映射为数字：A=0, C=1, G=2, T=3
   • 使用四进制数表示子串，如"ACGT" = 0×4³ + 1×4² + 2×4¹ + 3×4⁰ = 27
   • 哈希函数：h(s[i...i+9]) = Σ(s[i+k] × 4^(9-k))，其中k=0到9

4. 滚动哈希计算：

   • 第一个子串哈希：h0 = s[0]×4⁹ + s[1]×4⁸ + ... + s[9]×4⁰
   • 下一个子串哈希：h1 = (h0 - s[0]×4⁹) × 4 + s[10]×4⁰
   • 通用公式：h_{i+1} = (h_i - s[i]×4⁹) × 4 + s[i+10]

5. 具体实现步骤：

   • 如果序列长度小于10，直接返回空结果
   • 初始化哈希集合seen和结果集合result
   • 计算第一个长度为10的子串的哈希值
   • 遍历序列，对每个位置：
     a. 计算当前子串的哈希值（使用滚动哈希优化）
     b. 如果该哈希值已经在seen中出现过，将子串加入result
     c. 否则将哈希值加入seen
   • 返回result中的所有唯一子串

6. 哈希冲突处理：

   • 虽然四进制编码能减少冲突，但仍可能发生
   • 当发现重复哈希值时，需要实际比较子串内容确认是否真重复
   • 这保证了结果的绝对准确性

7. 复杂度分析：

   • 时间复杂度：O(n)，每个子串处理是常数时间
   • 空间复杂度：O(n)，需要存储所有出现过的子串信息

这种方法相比暴力解法有显著效率提升，特别适合处理长DNA序列中的重复模式查找。