class Solution {
public:
    const int d = 4;
    const int mod = 1000003;

    map<char, int> dna;
    map<int, int> m;

    vector<string> robin_karp(string& text) {
        vector<string> rez;

        dna['A'] = 0;
        dna['C'] = 1;
        dna['G'] = 2;
        dna['T'] = 3;

        int N = text.size();
        int M = 10;

        int hash_t = 0, h = 1;

        for (int i=0; i < M-1; i++) {
            h = (h * d);
        }

        for (int i=0; i < M; i++) {
            hash_t = ((hash_t * d) + dna[text[i]]);
        }

        int l = 0, r = M, cnt = 0;

        while (r <= N) {
            m[hash_t]++;
            if (m[hash_t] == 2)
                rez.push_back(text.substr(l, 10));

            if (r == N)
                break;

            hash_t = (hash_t - dna[text[l]] * h);
            hash_t = (hash_t * d + dna[text[r]]);

            if (hash_t < 0)
                hash_t += mod;

            l++;
            r++;
        }

        return rez;
    }

    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> rez = robin_karp(s);
        return rez;
    }
};