#include <cstdint>
#include <string>
#include <vector>
class Solution {
public:
std::vector<std::string> findRepeatedDnaSequences(std::string s) {
std::vector<std::string> repeated_sequences;
//char count[262143];
//memset(count, 0, 262143);
uint8_t count[262143] = {0};
uint32_t hash = 0;
const char *p = s.c_str();
for (size_t i = 0, end = s.size(); i < end; ++i) {
char c = s[i];
uint32_t val = 0;
switch (c) {
case 'A':
break;
case 'C':
val = 1;
break;
case 'G':
val = 2;
break;
case 'T':
val = 3;
break;
default:
return std::move(repeated_sequences);
}
hash = ((hash << 2) | val);
if (i < 9) {
continue;
}
hash &= 0x000fffff;
uint32_t bucket = (hash >> 2), index = ((hash & 3) << 1);
switch ((count[bucket] >> index) & 3) {
case 1:
if (i < (end - 1)) {
c = s[i + 1];
s[i + 1] = '\0';
repeated_sequences.emplace_back(p);
s[i + 1] = c;
} else {
repeated_sequences.emplace_back(p);
}
// fall through
case 0:
count[bucket] += (1 << index);
// fall through
default:
break;
}
++p;
}
return std::move(repeated_sequences);
}
};
#include <iostream>
int main() {
Solution sol;
auto ret = sol.findRepeatedDnaSequences("AAAAAAAAAAAA");
for (const auto &s : ret) {
std::cout << s << ": " << s.size() << std::endl;
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbnQ+CgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnN0cmluZz4gZmluZFJlcGVhdGVkRG5hU2VxdWVuY2VzKHN0ZDo6c3RyaW5nIHMpIHsKICAgICAgICBzdGQ6OnZlY3RvcjxzdGQ6OnN0cmluZz4gcmVwZWF0ZWRfc2VxdWVuY2VzOwogICAgICAgIC8vY2hhciBjb3VudFsyNjIxNDNdOwogICAgICAgIC8vbWVtc2V0KGNvdW50LCAwLCAyNjIxNDMpOwogICAgICAgIHVpbnQ4X3QgY291bnRbMjYyMTQzXSA9IHswfTsKICAgICAgICB1aW50MzJfdCBoYXNoID0gMDsKICAgICAgICBjb25zdCBjaGFyICpwID0gcy5jX3N0cigpOwogICAgICAgIGZvciAoc2l6ZV90IGkgPSAwLCBlbmQgPSBzLnNpemUoKTsgaSA8IGVuZDsgKytpKSB7CiAgICAgICAgICAgIGNoYXIgYyA9IHNbaV07CiAgICAgICAgICAgIHVpbnQzMl90IHZhbCA9IDA7CiAgICAgICAgICAgIHN3aXRjaCAoYykgewogICAgICAgICAgICBjYXNlICdBJzoKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICBjYXNlICdDJzoKICAgICAgICAgICAgICAgIHZhbCA9IDE7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgY2FzZSAnRyc6CiAgICAgICAgICAgICAgICB2YWwgPSAyOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIGNhc2UgJ1QnOgogICAgICAgICAgICAgICAgdmFsID0gMzsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICBkZWZhdWx0OgogICAgICAgICAgICAgICAgcmV0dXJuIHN0ZDo6bW92ZShyZXBlYXRlZF9zZXF1ZW5jZXMpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGhhc2ggPSAoKGhhc2ggPDwgMikgfCB2YWwpOwogICAgICAgICAgICBpZiAoaSA8IDkpIHsKICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGhhc2ggJj0gMHgwMDBmZmZmZjsKICAgICAgICAgICAgdWludDMyX3QgYnVja2V0ID0gKGhhc2ggPj4gMiksIGluZGV4ID0gKChoYXNoICYgMykgPDwgMSk7CiAgICAgICAgICAgIHN3aXRjaCAoKGNvdW50W2J1Y2tldF0gPj4gaW5kZXgpICYgMykgewogICAgICAgICAgICBjYXNlIDE6CiAgICAgICAgICAgICAgICBpZiAoaSA8IChlbmQgLSAxKSkgewogICAgICAgICAgICAgICAgICAgIGMgPSBzW2kgKyAxXTsKICAgICAgICAgICAgICAgICAgICBzW2kgKyAxXSA9ICdcMCc7CiAgICAgICAgICAgICAgICAgICAgcmVwZWF0ZWRfc2VxdWVuY2VzLmVtcGxhY2VfYmFjayhwKTsKICAgICAgICAgICAgICAgICAgICBzW2kgKyAxXSA9IGM7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHJlcGVhdGVkX3NlcXVlbmNlcy5lbXBsYWNlX2JhY2socCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAvLyBmYWxsIHRocm91Z2gKICAgICAgICAgICAgY2FzZSAwOgogICAgICAgICAgICAgICAgY291bnRbYnVja2V0XSArPSAoMSA8PCBpbmRleCk7CiAgICAgICAgICAgICAgICAvLyBmYWxsIHRocm91Z2gKICAgICAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgICsrcDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHN0ZDo6bW92ZShyZXBlYXRlZF9zZXF1ZW5jZXMpOwogICAgfQp9OwoKI2luY2x1ZGUgPGlvc3RyZWFtPgoKaW50IG1haW4oKSB7CiAgU29sdXRpb24gc29sOwogIGF1dG8gcmV0ID0gc29sLmZpbmRSZXBlYXRlZERuYVNlcXVlbmNlcygiQUFBQUFBQUFBQUFBIik7CiAgZm9yIChjb25zdCBhdXRvICZzIDogcmV0KSB7CiAgICBzdGQ6OmNvdXQgPDwgcyA8PCAiOiAiIDw8IHMuc2l6ZSgpIDw8IHN0ZDo6ZW5kbDsKICB9CiAgcmV0dXJuIDA7Cn0=