<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>

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        if len(s)<10:
            return []
        value_hash_set=set()
        added=set()
        frame_hash_value=0
        output=[]
        offset=64
        weight=0
        #alphabet_size=10000000
        #prime=44159
        alphabet_size=3337838838353
        prime=431604727
        alphabet_size=3337838838353557843
        prime=4316047271
        
        
        
        #print(len(s))
        
        for index in range(9,-1,-1):
        
            new_value=(((alphabet_size)**(weight))*((ord(s[index])-offset)))%prime
            
            frame_hash_value=(frame_hash_value+new_value)%prime
            #print(new_value,"new_value",frame_hash_value,"new_frame_hash_value")
            weight=weight+1
        value_hash_set.add(frame_hash_value)
        #print(frame_hash_value,"frame_hash_value")
        for index in range(10,len(s)):
            to_remove_value=(((alphabet_size)**(9))*((ord(s[index-10])-offset)))%prime
            #print(to_remove_value,"to_remove_value")
            frame_hash_value=frame_hash_value-to_remove_value
            #print(frame_hash_value,"after_removed")
            frame_hash_value=(frame_hash_value*alphabet_size)%prime
            
            to_add_value=(ord(s[index])-offset)
            #print(to_add_value,"to_add_value")
            frame_hash_value=(frame_hash_value+to_add_value)%prime
            #print(frame_hash_value,"frame_hash_value_after_added")
            if frame_hash_value in value_hash_set:
                
                if frame_hash_value not in added:
                    output.append(s[index-9:index+1])
                
                
                added.add(frame_hash_value)
            value_hash_set.add(frame_hash_value)

        return output
        
27200