<p>The <strong>DNA sequence</strong> is composed of a series of nucleotides abbreviated as <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;T&#39;</code>.</p>

<ul>
	<li>For example, <code>&quot;ACGAATTCCG&quot;</code> is a <strong>DNA sequence</strong>.</li>
</ul>

<p>When studying <strong>DNA</strong>, it is useful to identify repeated sequences within the DNA.</p>

<p>Given a string <code>s</code> that represents a <strong>DNA sequence</strong>, return all the <strong><code>10</code>-letter-long</strong> sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
<strong>Output:</strong> ["AAAAACCCCC","CCCCCAAAAA"]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "AAAAAAAAAAAAA"
<strong>Output:</strong> ["AAAAAAAAAA"]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, or <code>&#39;T&#39;</code>.</li>
</ul>

//rolling hash - rabin carp
// class Solution {
// public:
//     vector<string> findRepeatedDnaSequences(string s) {
//         if(s.length() <= 10) return {};
//         unordered_set<long long> uset;
//         vector<int> prime(26);
//         prime[0] = 1;
//         prime['C' - 'A'] = 2;
//         prime['G' - 'A'] = 3;
//         prime['T' - 'A'] = 5;
//         long long hash = 0;
//         for(int i = 0; i < 10; i++) {
//             hash = (hash*4) + prime[s[i] - 'A']; //
//             cout<<hash<<" ";
//         }
        
//         uset.insert(hash);
//         unordered_set<string> result;
//         for(int st = 0, en = 10; en < s.length(); st++, en++) {
//             //out
//             //hash = hash - 4^(en-st-1);//pow(4, (en-st-1)); //
//             //in
//             //hash = (hash*4) + prime[s[en] - 'A']; //
//             double pw=pow(4,10);
//             hash = hash * 4 - prime[s[st] - 'A'] * pw + prime[s[en] - 'A'];
//             cout<<hash<<" ";
//             if(uset.find(hash) != uset.end()) {
//                 result.insert(s.substr(st+1, 10));
                
//             }
//             else {
//                 uset.insert(hash);
//             }
//         }
//         return vector<string>(result.begin(), result.end());
//     }
// };



class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> st;
        double pw=pow(4,10);
        int n=s.length();
        int li[n];
        for(int i=0;i<n;i++){
            if(s[i]=='A'){
                li[i]=0;
            }
            else if(s[i]=='T'){
                li[i]=1;
            }
            else if(s[i]=='G'){
                li[i]=2;
            }
            else{
                li[i]=3;
            }
        }
        long long int hash_val=0;
        unordered_map<int,int>mp;
        for(int i=0;i<n-9;i++){
            if(i==0){
                for(int i=0;i<10;i++){
                    hash_val= 4*hash_val + li[i]; //converting to decimal number  
                }
                mp[hash_val]++;
            }
            else{
                hash_val = hash_val * 4 - li[i - 1] * pw + li[i + 9]; // Finding new hash value 
                mp[hash_val]++;
                if(mp[hash_val]==2){
                    st.push_back(s.substr(i,10));
                }
            }
        }
        return st;
    }
};

14828