C++で繰り返されるDNA配列

DNA分子に複数回出現する10文字の長さのシーケンス（サブストリング）をすべて見つけるには、1つのメソッドを作成する必要があります。

したがって、入力が「AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT」の場合、出力は["AAAAACCCCC"、"CCCCCAAAAA"]になります。

これを解決するには、次の手順に従います-

• 配列ret、n：=sのサイズを定義し、visitedとvisited2という2つのセットを作成します

• bitValというマップを定義します。

• 0123などのACGTに対応する値をbutValに保存します。

• マスク：=0

• 0からn–1の範囲のiの場合

  • マスク：=マスク* 4

  • マスク：=マストまたはbitVal [s [i]]

  • マスク：=マスクとFFFFF

  • i <9の場合は、次の反復に進みます

    • 部分文字列フォームインデックスi–9から9をretに挿入します

    • マークをvisited2に挿入します。

  • 訪問者にマスクを挿入

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