Rabin-Karp算法在重复DNA序列查找中的应用 题目描述： 给定一个字符串 s 表示DNA序列（仅包含 'A', 'C', 'G', 'T' 四种字符），要求找出所有长度为 10 且出现超过一次的重复子串。例如，对于 s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"，应返回 [ "AAAAACCCCC", "CCCCCAAAAA" ]。 解题步骤： 问题分析 DNA序列仅包含4种字符，可映射为数字（例如 A=0, C=1, G=2, T=3）。需要高效查找长度为10的重复子串，直接暴力枚举所有子串（O(n×10)）并存储出现位置会占用大量空间。Rabin-Karp算法通过滚动哈希在O(1)时间内计算相邻子串的哈希值，从而将时间复杂度优化至O(n)。 哈希函数设计 将字符串视为四进制数，例如子串 "ACG" 可转换为 \(0×4^2 + 1×4^1 + 2×4^0\)。但实际计算时需避免大整数溢出，采用取模运算（模数选较大质数，如 \(10^9+7\)）。具体哈希函数为： \[ \text{hash} = (c_ 0 \times 4^9 + c_ 1 \times 4^8 + \dots + c_ 9 \times 4^0) \mod M \] 其中 \(c_ i\) 为字符对应的数字（0-3）。 滚动哈希计算 设当前子串 s[ i: i+10] 的哈希值为 \(h_ i\)，则下一个子串 s[ i+1: i+11 ] 的哈希值可通过以下步骤计算： 移除首字符贡献：\(h_ i - (c_ i \times 4^9) \mod M\) 结果乘以4（四进制左移一位）：\([ h_ i - c_ i \times 4^9 ] \times 4 \mod M\) 加上新字符 \(c_ {i+10}\)：\(h_ {i+1} = ([ h_ i - c_ i \times 4^9] \times 4 + c_ {i+10}) \mod M\) 此过程仅需O(1)时间，避免重新计算整个子串的哈希值。 处理哈希冲突 尽管哈希值可能冲突，但DNA序列长度10的子串实际冲突概率极低。为严谨性，当两个子串哈希值相同时，需比较字符串内容是否真的一致（防止假阳性）。 算法实现步骤 初始化哈希表 seen 和结果集 res。 预计算 \(4^9 \mod M\) 避免重复计算。 计算第一个长度为10的子串的哈希值 \(h_ 0\)。 遍历 i 从 0 到 n-10： 若当前哈希值已在 seen 中出现过，且子串内容匹配，则将子串加入 res。 否则将哈希值及子串索引存入 seen。 若 i < n-10，用滚动哈希计算 \(h_ {i+1}\)。 返回 res。 复杂度分析 时间复杂度：O(n)，每个子串处理时间为O(1)。 空间复杂度：O(n)，哈希表存储最多 n-9 个子串的索引。 此方法通过滚动哈希高效检测重复模式，适用于DNA序列等固定长度模式匹配场景。