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]]

• 遮罩：=遮罩AND FFFFF

• 如果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, ]