Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created August 4, 2019 07:47
Show Gist options
  • Save jianminchen/a18664352e0d9c16a9989ad7f0803dc5 to your computer and use it in GitHub Desktop.
Save jianminchen/a18664352e0d9c16a9989ad7f0803dc5 to your computer and use it in GitHub Desktop.
Rabin karp algorithm to study
/// <summary>
/// Rabin Karp string search algorithm.
/// </summary>
/// <param name="haystack">The haystack.</param>
/// <param name="needle">The needle.</param>
/// <returns>The list of index.</returns>
public static List<int> RabinKarp(string haystack, string needle)
{
var result = new List<int>();
if (string.IsNullOrWhiteSpace(haystack) || string.IsNullOrWhiteSpace(needle) || (needle.Length > haystack.Length)) return result;
int m = needle.Length, n = haystack.Length, needleHash = 0, haystackHash = 0, mostSignificantDigitHash = 1; ;
const int Mod = 101, NumberBase = 256;
for (int i = 0; i < m - 1; i++) // The value of h would be "pow(NumberBase, m-1)%q"
mostSignificantDigitHash = (mostSignificantDigitHash * NumberBase) % Mod;
for (int i = 0; i < m; i++)
{
needleHash = ((NumberBase * needleHash) + needle[i]) % Mod;
haystackHash = ((NumberBase * haystackHash) + haystack[i]) % Mod;
}
for (int i = 0; i <= n - m; i++)
{
if (needleHash == haystackHash)
{
for (int j = 0; j <= m; j++)
{
if (j == m) result.Add(i);
else if (haystack[i + j] != needle[j]) break;
}
}
if (i < n - m)
{
haystackHash = ((NumberBase * (haystackHash - (haystack[i] * mostSignificantDigitHash))) + haystack[i + m]) % Mod;
if (haystackHash < 0) haystackHash = (haystackHash + Mod);
}
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment