C# rolling hash implementation


  • 0
    C

    C# rolling hash implementation

            public IList<string> FindRepeatedDnaSequences(string s)
            {
                List<string> result = new List<string>();
    
                if (s.Length < 10)
                {
                    return result;
                }
    
                Dictionary<int, int> d = new Dictionary<int, int>(s.Length - 10);
    
                int rollingHash = 0;
                int i = 0;
    
                while (i < 9)
                {
                    rollingHash = rollingHash << 3 | s[i++] & 7;
                }
    
                while (i < s.Length)
                {
                    rollingHash = rollingHash << 3 & 0X3FFFFFFF | s[i++] & 7;
                    if (d.ContainsKey(rollingHash))
                    {
                        if (d[rollingHash]++ == 1)
                        {
                            result.Add(s.Substring(i - 10, 10));
                        }
                    }
                    else
                    {
                        d.Add(rollingHash, 1);
                    }
                }
    
                return result;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.