Demonstrate an example for Rabin Karp algorithm?

Software Development
#1

Problem Statement:

Given a text txt[0…n-1] and a pattern pat[0…m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m

Example:

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Initially, we discuss the strategy which is checking the pattern by moving window one by one, but without checking all characters for all cases (finding the hash value).

When the hash value is matched, then only it tries to check each character.

Pseudo Code: -

   for i := 0 to (lenStr - patLen), do
      if patHash = strHash, then
         for charIndex := 0 to patLen -1, do
            if text[i+charIndex] ≠ pattern[charIndex], then
               break the loop
         if charIndex = patLen, then
            print the location i as pattern found at i position.
      if i < (lenStr - patLen), then
         strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then
      if strHash < 0, then
         strHash := strHash + prime