重复DNA序列

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

解题过程：

1. 问题分析：

• DNA序列由4种字符组成，我们需要找到所有长度为10的重复子串
• 子串出现超过一次就需要被记录
• 返回结果中不应包含重复的子串

2. 暴力解法的问题：

• 直接枚举所有长度为10的子串，用哈希表统计出现次数
• 时间复杂度O(10n)，但字符串可能很长，10n的常数因子较大
• 每个子串长度为10，存储和比较开销较大

3. 优化思路：使用滚动哈希

• 将DNA字符映射为数字：A=0, C=1, G=2, T=3
• 使用四进制数表示子串，将字符串转换为数字
• 通过滚动哈希，可以在O(1)时间内计算下一个子串的哈希值

4. 具体实现步骤：
   步骤1：字符映射

• 建立映射关系：{'A':0, 'C':1, 'G':2, 'T':3}

步骤2：计算第一个子串的哈希值

• 对于前10个字符，按四进制计算：
  hash = c₀×4⁹ + c₁×4⁸ + ... + c₉×4⁰

步骤3：滚动计算后续哈希值

• 当窗口向右滑动时，新的哈希值：
  new_hash = (old_hash - 第一个字符×4⁹) × 4 + 新字符

步骤4：处理哈希冲突

• 虽然四进制映射可以大大减少冲突，但仍需处理
• 当哈希值相同时，需要实际比较字符串内容

5. 完整算法：

6. 如果字符串长度小于等于10，返回空列表

7. 创建字符到数字的映射表

8. 计算4⁹的值（预计算避免重复计算）

9. 使用哈希表记录每个哈希值对应的子串起始位置

10. 计算第一个长度为10的子串的哈希值

11. 滑动窗口遍历整个字符串：

    • 更新哈希值
    • 检查该哈希值是否已出现
    • 如果出现，验证是否为真正重复（解决哈希冲突）
    • 记录重复的子串

12. 返回结果列表

13. 时间复杂度分析：

• 每个子串的哈希计算：O(1)
• 总体时间复杂度：O(n)
• 空间复杂度：O(n)，用于存储哈希表

这种方法通过滚动哈希将时间复杂度从O(10n)优化到O(n)，在处理长DNA序列时效率显著提升。