s4553711
5/6/2017 - 6:58 AM

187.cpp

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> ans;
        map<int, int> mp;
        map<char, int> cur;
        set<string> st;
        cur['A'] = 0;
        cur['T'] = 1;
        cur['C'] = 2;
        cur['G'] = 3;
        if (s.length() < 10) return ans;
        int temp = 0;
        for(int i = 0;i < 10; i++){
            temp <<= 2;
            temp |= cur[s[i]];
        }
        mp[temp]++;
        for(int i = 10; i < s.length(); i++){
            temp <<= 2;
            temp &= ~(0x300000);
            temp |= cur[s[i]];
            mp[temp]++;
            if (mp[temp]>=2) {
                st.insert(s.substr(i-9, 10));
            }
        }
        set<string>::iterator it;
        for(it = st.begin(); it != st.end(); it++) {
            ans.push_back(*it);
        }
        return ans;
    }
};