Skip to content

Instantly share code, notes, and snippets.

@ThuyNT13
Last active November 5, 2018 10:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ThuyNT13/8ac4c0d5dfa1e9f1a8c8384433bd23cd to your computer and use it in GitHub Desktop.
Save ThuyNT13/8ac4c0d5dfa1e9f1a8c8384433bd23cd to your computer and use it in GitHub Desktop.
implement a Rolling Hash in C#
/*
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 = "<b$@cz/> <%!~z/> <defghcaz/>";
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<str.Length; i++) {
first = str[i-patternLen];
char next = str[i];
double firstHash = CalculateCharHash(first, 0);
double nextHash = CalculateCharHash(next, patternLen-1);
// Console.WriteLine(subStringHash+" - "+firstHash );
subStringHash -= firstHash;
// Console.WriteLine(subStringHash+ " / " +primeBase);
subStringHash /= primeBase;
// Console.WriteLine(subStringHash+ " + " +nextHash);
subStringHash += nextHash;
Console.WriteLine("subStringHash total: "+subStringHash);
CompareSubstringHash(subStringHash, patternHash);
}
return false;
}
private static double CalculateCharHash(char c, int power) {
return c * (Math.Pow(primeBase, power));
}
private static double CalculateSubstringHash(string subStr) {
double totalHash = 0;
int substrLen = subStr.Length;
for (int i=0; i<substrLen; i++) {
char c = subStr[i];
totalHash += CalculateCharHash(c, i);
}
return totalHash;
}
private static bool CompareSubstringHash(double subStringHash, double patternHash) {
if (subStringHash == patternHash) {
Console.WriteLine("true");
return true;
}
return false;
}
}
@ThuyNT13
Copy link
Author

ThuyNT13 commented Nov 5, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment