ivandrofly

rabin karp substring search algo O(m+n)

Mar 4th, 2021
788
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. namespace RabinKarpSubstringSearch
  2. {
  3.     using System;
  4.  
  5.     class Program
  6.     {
  7.  
  8.         private const int Prime = 31;
  9.  
  10.         static void Main(string[] args)
  11.         {
  12.             Console.WriteLine("Hello World!");
  13.             string pattern = "foo";
  14.             int patternHash = CalcHash(pattern);
  15.  
  16.             int pos = IsMatch("hello _foobar", patternHash, pattern.Length);
  17.             if (pos != 1)
  18.             {
  19.                 Console.WriteLine("Tadaaa! " + pos);
  20.             }
  21.  
  22.             Console.ReadLine();
  23.         }
  24.  
  25.         private static int CalcHash(string pattern)
  26.         {
  27.             int hashValue = 0;
  28.             int len = pattern.Length;
  29.             //for (int i = 0; i < len; i++)
  30.             //{
  31.             //    hashValue += Convert.ToInt32(pattern[i]) * (int)Math.Pow(Prime, i);
  32.             //}
  33.             int i = 0;
  34.             while (i < len)
  35.             {
  36.                 hashValue += Convert.ToInt32(pattern[i]) * (int)Math.Pow(Prime, i);
  37.                 i++;
  38.             }
  39.             return hashValue;
  40.         }
  41.  
  42.         private static int IsMatch(string text, int patternHash, int lenPattern)
  43.         {
  44.             int i = 0;
  45.             // compute 1st hash from 0 to lenghth of pattern -1
  46.             int textHash = 0;
  47.             while (i < lenPattern)
  48.             {
  49.                 textHash += Convert.ToInt32(text[i]) * (int)Math.Pow(Prime, i);
  50.                 i++;
  51.             }
  52.  
  53.             // check match found at position 0
  54.             if (patternHash == textHash)
  55.             {
  56.                 return 0;
  57.             }
  58.  
  59.             // compute and comparing the the hashes
  60.             int len = text.Length;
  61.             while (i < len)
  62.             {
  63.                 int k = i;
  64.  
  65.                 // note: this is quite easy to understand
  66.                 // https://www.youtube.com/watch?v=H4VrKHVG5qI&t=324s
  67.                 textHash = (textHash - Convert.ToInt32(text[i - lenPattern])) / Prime + Convert.ToInt32(text[i]) * (int)Math.Pow(Prime, lenPattern - 1);
  68.                 if (patternHash == textHash)
  69.                 {
  70.                     // return the index. k is index of last letter in pattern so return back length of pattern - 1 (-1 is that we are already in the last letter of the pattern)
  71.                     return k - lenPattern - 1;
  72.                 }
  73.                 i++;
  74.             }
  75.  
  76.             return -1;
  77.         }
  78.     }
  79. }
  80.  
  81. // explanation: https://www.youtube.com/watch?v=H4VrKHVG5qI&t=324s
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×