Instantly share code, notes, and snippets.

# ThuyNT13/RollingHash.cs

Last active November 5, 2018 10:58
Star You must be signed in to star a gist
implement a Rolling Hash in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* First calculate the hash of first *n* letter substring (abcd) in string. Iterate through string, starting at index of next (= pattern length): subString = (first + subSubstring) + next 1. drop a (first) (a*7^0 + b*7^1 + c*7^2 + d*7^3) - a*7^0 2. divide everything by 7 (b*7^1 + c*7^2 + d*7^3) / 7 => b*7^0 + c*7^1 + d*7^2 3. add d (next) (b*7^0 + c*7^1) + d*7^2 Compare substringHash to patternHash substring1 = a*7^0+ b*7^1+c*7^2=97*1+98*7+99*49=5634 pattern = b*7^0+ c*7^1+d*7^2=98*1+99*7+100*49=5691 Not yet implemented: * to avoid overflow because of large power, we will have to do modulo with large prime References: https://www.quora.com/What-is-a-rolling-hash-and-when-is-it-useful Math.Pow(double base, double power) */ using System; class RollingHash { private static readonly int primeBase = 7; public static void Main (string[] args) { string pattern = "~z/>"; string str = " <%!~z/> "; RollingHashIterator(str, pattern); } internal static bool RollingHashIterator(string str, string pattern) { int patternLen = pattern.Length; string subString = str.Substring(0, patternLen); char first = subString[0]; double patternHash = CalculateSubstringHash(pattern); Console.WriteLine("pattern hash: " +patternHash); // First calculate the hash of first *n* letter substring in string. double subStringHash = CalculateSubstringHash(subString); CompareSubstringHash(subStringHash, patternHash); for (int i=patternLen; i

### ThuyNT13 commented Nov 5, 2018

@mtroiani here's my rolling hash. appreciate any feedback