C ++中的重复DNA序列
我们必须编写一种方法来查找在DNA分子中出现多次的所有10个字母长的序列（子串）。
因此，如果输入类似于“AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”，那么输出将为[“AAAAACCCCC”，“CCCCCAAAAA”]。
为了解决这个问题，我们将遵循以下步骤-
定义一个数组ret，n：=s的大小，创建两个名为visited和visited2的集合
定义一个名为bitVal的映射。
将ACGT的对应值（如0123）存储到butVal中。
遮罩：=0
对于i，范围为0至n–1
将子字符串形式的索引i–9到9插入ret
将标记插入Visited2。
面具：=面具*4
掩码：=桅杆或bitVal[s[i]]
遮罩：=遮罩ANDFFFFF
如果i<9，则继续下一个迭代
将遮罩插入已访问
返回ret
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
vector<string>findRepeatedDnaSequences(string s) {
vector <string> ret;
int n = s.size();
set <int> visited;
set <int> visited2;
map <char, int> bitVal;
bitVal['A'] = 0;
bitVal['C'] = 1;
bitVal['G'] = 2;
bitVal['T'] = 3;
lli mask = 0;
for(int i = 0; i < n; i++){
mask <<= 2;
mask |= bitVal[s[i]];
mask &= 0xfffff;
if(i < 9) continue;
if(visited.count(mask) && !visited2.count(mask)){
ret.push_back(s.substr(i - 9, 10));
visited2.insert(mask);
}
visited.insert(mask);
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
}输入值
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出结果
[AAAAACCCCC, CCCCCAAAAA, ]