LeetCode 187. Repeated DNA Sequences(位运算，hash)

class Solution {
public:
    int m[1<<21];
    int m3[1<<21];
    int m2[127];
    char m4[4];
    vector<string> findRepeatedDnaSequences(string s) {
        
        m2['A']=0;
        m2['C']=1;
        m2['G']=2;
        m2['T']=3;
        
        m4[0]='A';
        m4[1]='C';
        m4[2]='G';
        m4[3]='T';
        
        int x=0;
        for(int i=0;i<10&&i<s.length();i++)
        {
            x<<=2;
            x |= m2[s[i]];
            
        }
        
        m[x]=1;
        
        int y = (1<<18)-1;
        
        vector<string> ans;
        
        for(int i=10;i<s.length();i++)
        {
            x &= y;
            
            x <<= 2;
            
            x |= m2[s[i]];
            
            m[x]++;
            
            if(m[x]>1 && m3[x]==0)
            {
               ans.push_back(fun(x));
               m3[x]=1;
            }
            
        }
        
        return ans;
        
    }
    
    string fun(int x)
    {
        string s="";
        int y ;
        for(int i=19;i>=1;i-=2)
        {
            y = (1 << i) | ( 1<<(i-1));
            int z = x&y;
            z >>= (i-1);
            s+=m4[z];
        }
        
        return s;
    }
};