Advertisement
Martin_Toseski

Untitled

Nov 29th, 2023
645
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     const int d = 4;
  4.     const int mod = 1000003;
  5.  
  6.     map<char, int> dna;
  7.     map<int, int> m;
  8.    
  9.     vector<string> robin_karp(string& text) {
  10.         vector<string> rez;
  11.  
  12.         dna['A'] = 0;
  13.         dna['C'] = 1;
  14.         dna['G'] = 2;
  15.         dna['T'] = 3;
  16.  
  17.         int N = text.size();
  18.         int M = 10;
  19.  
  20.         int hash_t = 0, h = 1;
  21.  
  22.         for (int i=0; i < M-1; i++) {
  23.             h = (h * d);
  24.         }
  25.  
  26.         for (int i=0; i < M; i++) {
  27.             hash_t = ((hash_t * d) + dna[text[i]]);
  28.         }
  29.  
  30.         int l = 0, r = M, cnt = 0;
  31.  
  32.         while (r <= N) {
  33.             m[hash_t]++;
  34.             if (m[hash_t] == 2)
  35.                 rez.push_back(text.substr(l, 10));
  36.  
  37.             if (r == N)
  38.                 break;
  39.  
  40.             hash_t = (hash_t - dna[text[l]] * h);
  41.             hash_t = (hash_t * d + dna[text[r]]);
  42.  
  43.             if (hash_t < 0)
  44.                 hash_t += mod;
  45.            
  46.             l++;
  47.             r++;
  48.         }
  49.  
  50.         return rez;
  51.     }
  52.  
  53.     vector<string> findRepeatedDnaSequences(string s) {
  54.         vector<string> rez = robin_karp(s);
  55.         return rez;
  56.     }
  57. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement