"""
QUESTION:
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
ANSWER:
hash
"""
class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        map = {'A':0, 'C':1, 'G':2, 'T':3}
        sum = 0
        ans = []
        d = dict()
        for i in xrange(len(s)):
            sum = (sum*4+map[s[i]])&0xFFFFF
            if i < 9:
                continue
            part = s[i:i+10]
            d[sum] = d.get(sum,0) + 1
            if d[sum] == 2:
                ans.append(s[i-9:i+1])
        return ans

if __name__ == '__main__':
    print Solution().findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")