/
RepeatedDNASequences.cpp
58 lines (54 loc) · 1.29 KB
/
RepeatedDNASequences.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
*Repeated DNA Sequences
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<vector>
#include<map>
#include<stdlib.h>
#define Code 0x3ffff
using namespace std;
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int size = s.size();
vector<string> res;
if(size <= 10)
return res;
map<int, int> myMap;
map<char, int> char2int; // = {{'A',0},{'C',1},{'G',2},{'T',3}};
char2int['A'] = 0;
char2int['C'] = 1;
char2int['G'] = 2;
char2int['T'] = 3;
int strInt = 0;
for(int i=0;i<10;i++){
strInt = (strInt << 2) + char2int[s[i]];
}
myMap[strInt] = 1;
for(int i=10; i<size; i++){
strInt = ((strInt & Code) << 2) + char2int[s[i]];
if(myMap.find(strInt) == myMap.end())
myMap[strInt] = 1;
else{
if(myMap[strInt] == 1){
string substr = s.substr(i-9,10);
res.push_back(substr);
}
myMap[strInt] ++;
}
}
return res;
}
};
int main(){
Solution s;
string str("GAGAGAGAGAGA");
vector<string> res = s.findRepeatedDnaSequences(str);
for(int i=0;i<res.size();i++){
cout<<res[i]<<endl;
}
system("pause");
return 0;
}