fork download
copy 
  1. #include <cstdint>
  2.  
  3. #include <string>
  4. #include <vector>
  5.  
  6. class Solution {
  7. public:
  8.     std::vector<std::string> findRepeatedDnaSequences(std::string s) {
  9.         std::vector<std::string> repeated_sequences;
  10.         //char count[262143];
  11.         //memset(count, 0, 262143);
  12.         uint8_t count[262143] = {0};
  13.         uint32_t hash = 0;
  14.         const char *p = s.c_str();
  15.         for (size_t i = 0, end = s.size(); i < end; ++i) {
  16.             char c = s[i];
  17.             uint32_t val = 0;
  18.             switch (c) {
  19.             case 'A':
  20.                 break;
  21.             case 'C':
  22.                 val = 1;
  23.                 break;
  24.             case 'G':
  25.                 val = 2;
  26.                 break;
  27.             case 'T':
  28.                 val = 3;
  29.                 break;
  30.             default:
  31.                 return std::move(repeated_sequences);
  32.             }
  33.             hash = ((hash << 2) | val);
  34.             if (i < 9) {
  35.                 continue;
  36.             }
  37.             hash &= 0x000fffff;
  38.             uint32_t bucket = (hash >> 2), index = ((hash & 3) << 1);
  39.             switch ((count[bucket] >> index) & 3) {
  40.             case 1:
  41.                 if (i < (end - 1)) {
  42.                     c = s[i + 1];
  43.                     s[i + 1] = '\0';
  44.                     repeated_sequences.emplace_back(p);
  45.                     s[i + 1] = c;
  46.                 } else {
  47.                     repeated_sequences.emplace_back(p);
  48.                 }
  49.                 // fall through
  50.             case 0:
  51.                 count[bucket] += (1 << index);
  52.                 // fall through
  53.             default:
  54.                 break;
  55.             }
  56.             ++p;
  57.         }
  58.         return std::move(repeated_sequences);
  59.     }
  60. };
  61.  
  62. #include <iostream>
  63.  
  64. int main() {
  65.   Solution sol;
  66.   auto ret = sol.findRepeatedDnaSequences("AAAAAAAAAAAA");
  67.   for (const auto &s : ret) {
  68.     std::cout << s << ": " << s.size() << std::endl;
  69.   }
  70.   return 0;
  71. }
Success #stdin #stdout 0s 3408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
AAAAAAAAAA: 10
https://ideone.com/CVSgNc
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!