The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
"ACGAATTCCG" is a DNA sequence.When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
Example 2:
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
Constraints:
1 <= s.length <= 105s[i] is either 'A', 'C', 'G', or 'T'.题意：所有 DNA 都由一系列缩写为 ‘A’，‘C’，‘G’ 和 ‘T’ 的核苷酸组成，例如 “ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
由于数据范围只有 1 0 5 10^5 105 、目标子串长度为 10 10 10 ，一个朴素解法是：从左到右处理字符串 s s s ，使用固定长度为 10 10 10 的滑动窗口得到每个以 s [ i ] s[i] s[i] 开头且长度为 10 10 10 的子串，同时使用哈希表记录每个子串的出现次数，如果该子串出现次数超过一次，则加入答案——为了「避免其后再次遍历哈希表」（即只使用一次循环），同时「防止在一次遍历中重复添加相同子串」，我们规定，当且仅当该子串之前出现过一次、加上本次后出现次数为两次时，将该子串加入答案。
实际代码如下。由于每次要检查以 s [ i ] s[i] s[i] 开头、长度为 10 10 10 的字符串，时间复杂度为 O ( n C ) O(n C) O(nC) ，其中 C = 10 C = 10 C=10 。由于长度固定的子串数量不会超过 n n n 个，所以空间复杂度为 O ( n C ) O(nC) O(nC) ，其中 C = 10 C = 10 C=10 。
//C++ version
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string, int> rec;
vector<string> ans;
for (int i = 0, n = s.size(); i + 10 <= n; ++i) {
string &&cur = s.substr(i, 10); // 使用右值引用避免不必要的拷贝赋值调用
int &cnt = rec[cur]; //节省再次查找的时间
if (cnt == 1) ans.push_back(cur);
++cnt;
}
return ans;
}
};
//执行用时：44 ms, 在所有 C++ 提交中击败了85.74% 的用户
//内存消耗：22.9 MB, 在所有 C++ 提交中击败了16.66% 的用户
如果题目给定的子串长度大于 100 100 100 ，加上生成子串和哈希表本身的常数操作，解法1的计算量将超过 1 0 7 10^7 107 ，绝对会TLE。为了严格做到 O ( n ) O(n) O(n) 时间，需要使用字符串哈希+滚动哈希对解法1进行优化。
具体来说，这里使用一个与字符串 s s s 等长的哈希数组 h a s h [ ] hash[] hash[] 和 次方数组 p [ ] p[] p[] ，通过预处理字符串，我们先用 O ( n ) O(n) O(n) 时间计算出哈希数组和次方数组。需要实际计算子串 s [ i . . . j ] s[i...j] s[i...j] 的哈希值时，只需要计算 h a s h [ j ] − h a s h [ i − 1 ] ∗ p [ j − i + 1 ] hash[j] - hash[i - 1] * p[j - i + 1] hash[j]−hash[i−1]∗p[j−i+1] ，即可在 O ( 1 ) O(1) O(1) 时间内得出子串 s [ i . . . j ] s[i...j] s[i...j] 的哈希值（与子串长度无关），接着用哈希表统计这一哈希值出现的次数……随后的做法和解法1完全一致。
可以看到，随着循环变量
i
i
i 的不断增大，我们滚动向前计算以
i
i
i 为起点、长度为
10
10
10 的子串的哈希值，这一技巧称为「滚动哈希」，常与「字符串哈希」相关技巧一起使用。通过使用滚动哈希+字符串哈希，我们可以在
O
(
1
)
O(1)
O(1) 时间内计算出某个子串的哈希值，让进行计数的哈希表不必以 string 作为 key ，而是使用 int（即哈希值结果本身）作为 key ，从而避免了哈希表内部对「重叠子串」哈希值的重复计算，大大提高了算法的效率。
实际代码如下所示，时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( n ) O(n) O(n) 。
//C++ version
class Solution {
private:
static const int maxn = 1e5 + 10;
unsigned P = 131313;
unsigned hash[maxn] = {0}, p[maxn] = {1};
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.size();
vector<string> ans;
for (int i = 1; i <= n; ++i) {
hash[i] = hash[i - 1] * P + s[i - 1];
p[i] = p[i - 1] * P;
}
unordered_map<unsigned, int> rec;
for (int i = 1; i <= n - 10 + 1; ++i) {
int j = i + 10 - 1; // [i,j]标志这一长度为10的子串区间
unsigned seqHash = hash[j] - hash[i - 1] * p[j - i + 1]; // p[10]
int &cnt = rec[seqHash];
if (cnt == 1) ans.push_back(s.substr(i - 1, 10));
++cnt;
}
return ans;
}
};
//执行用时：28 ms, 在所有 C++ 提交中击败了96.65% 的用户
//内存消耗：16 MB, 在所有 C++ 提交中击败了80.48% 的用户
这样的优化已经足够强大，不过由于本题中要计算哈希值的子串具有固定的长度，我们完全可以节省掉 p [ ] p[] p[] 的计算，代之以变量 p 10 p10 p10 ：
//C++ version
class Solution {
private:
static const int maxn = 1e5 + 10;
unsigned P = 131313;
unsigned hash[maxn] = {0}, p10 = 40769121;
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.size();
vector<string> ans;
for (int i = 1; i <= n; ++i)
hash[i] = hash[i - 1] * P + s[i - 1];
unordered_map<unsigned, int> rec;
for (int i = 1; i <= n - 10 + 1; ++i) {
int j = i + 10 - 1; // [i,j]标志这一长度为10的子串区间
unsigned seqHash = hash[j] - hash[i - 1] * p10;
int &cnt = rec[seqHash];
if (cnt == 1) ans.push_back(s.substr(i - 1, 10));
++cnt;
}
return ans;
}
};
//执行用时：28 ms, 在所有 C++ 提交中击败了96.65% 的用户
//内存消耗：15.5 MB, 在所有 C++ 提交中击败了82.18% 的用户
到这里，本题就做完了，只是有些疑问要解决。字符串哈希在「构造数组」和「计算哈希」的过程中，不会溢出吗？肯定会溢出！这就是为什么我使用的是 unsigned int 而非 int ，因为 unsigned 溢出后相当于对
2
32
2^{32}
232 取模，C++不会报错。
使用哈希值代替该子串，在哈希表中查询出现次数时，不会出现哈希冲突吗？可能会冲突！两个 unsigned 类型的哈希值模
2
32
2^{32}
232 同余时，就会产生错误结果（哈希冲突），此时要考虑修改
P
P
P 或者使用表示范围更大的数据类型来替代 unsigned（不治本） 。至于这个数字
P
=
131313
P = 131313
P=131313 是如何产生的呢？首先
P
P
P 一定要是素数，然后从
131
,
13131
131, 13131
131,13131 一路尝试着WA过来得到的。关于质数表，可见。
其实以一般的眼光来看，解法2第二版已经高效到不能再高效了。不过算法的优化难有止境，这里有（比解法2）更高效的一种算法。当然，其本质也是对解法2的再度优化。
我们以挑刺的眼光看待解法2，发现有以下问题：
其实，对 A , C , G , T A, C, G, T A,C,G,T 四个字符可用 0 , 1 , 2 , 3 0, 1, 2, 3 0,1,2,3 即二进制的 00 , 01 , 10 , 11 00, 01, 10, 11 00,01,10,11 来表示，于是长度为 10 10 10 的字符串可用 20 20 20 位的二进制数表示。相对解法2，此解法的优势在于：
bitset 来存储，只需要
32768
32768
32768 个 int ；由于要确定至少出现过两次，就需要两个 bitset 即
65536
65 536
65536 个 int 。比起解法2来说，使用空间大幅减少，因为对哈希数组、次方数组和哈希表，全代之以两个 bitset算法的流程也是一致的，从左到右遍历字符串 s s s ，使用固定长度为 10 10 10 的滑动窗口，滚动计算每个以 s [ i ] s[i] s[i] 结尾且长度为 10 10 10 的子串对应的二进制数，接着用位图表示这一二进制数出现的次数……随后的做法和解法1、2几乎一致。
//C++ version
class Solution {
private: // 对应二进制数{00,01,10,11},那么长度为10的子串只要20位即可表示
unordered_map<char, int> rec = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
public:
vector<string> findRepeatedDnaSequences(string s) {
if (s.size() < 10) return {};
vector<string> ans;
bitset<1 << 20> s1, s2; // 所有可能子串的二进制数值在0到(1 << 20 - 1)之间
int n = s.size(), val = 0, mask = (1 << 20) - 1; // mask为二进制数的20个1
// 使用滑动窗口+滚动计算,先把前10个字母的二进制数计算出来
for (int i = 0; i < 10; ++i) val = (val << 2) | rec[s[i]];
s1.set(val); // 置位,表示前10个字母组成的子串已经出现
for (int i = 10; i < n; ++i) {
val = ((val << 2) & mask) | rec[s[i]]; // 去掉左移的一个字符,再加上一个新字符
if (s2.test(val)) continue; // 出现过两次则跳过
if (s1.test(val)) { // 出现了一次
ans.push_back(s.substr(i - 9, 10));
s2.set(val); // 表示出现了第二次
} else s1.set(val); // 表示出现了一次
}
return ans;
}
};
//执行用时：4 ms, 在所有 C++ 提交中击败了99.82% 的用户
//内存消耗：7.4 MB, 在所有 C++ 提交中击败了98.33% 的用户
可以看到，虽然和解法2一样都是 O ( n ) O(n) O(n) 时空复杂度的算法，但是二者的常数差距较大，且解法3的效率比较稳定。