Last active
July 27, 2024 15:10
-
-
Save ThuyNT13/8ac4c0d5dfa1e9f1a8c8384433bd23cd to your computer and use it in GitHub Desktop.
implement a Rolling Hash in C#
This file contains hidden or 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 = "<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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@mtroiani here's my rolling hash. appreciate any feedback