Question

Perform Rabin-Karp search on text 011010011001110 with pattern 111 and q = 6 and explain your results.

Answer 1

Here pattern length (m) = 3

Text length (n) = 6

q = 6 which is used as base of powers in the hash function.

Rabin-Karp works on hash function let's define the hash function for this->

6⁰ * no. present at index 0 of the sub-string of the given text + 6¹*no. present at index 1 of the sub-string of the given text + 6² * no. present at index 2 of the sub-string of the given text.

The value we got using the above hash function is called hash value.

The above hash function takes power up-to 2 because the length of the pattern to match is 3 i.e 0, 1, 2 are 3 powers. The hash function taken for each sub- string from the start rolled towards the end of the given text also known as rolling hash function.

First sub-string from the given text of length 3 is taken because pattern length is also 3 and we take the next sub-string by sliding on by 1 value that is first is 011, next will 110 and so on.

011 010 011 001 110

Above I show the distribution of given text into sub-string of length 3

Hash value for the pattern is :

6⁰ * 1 + 6¹ * 1 + 6² * 1

1 + 6 + 36

43

Now, let's find out hash function for 1st sub-string that is 011->

6⁰ * 0 + 6¹ * 1 + 6² * 1

0 + 6 + 36

42 which is not equal to pattern hash value that is 43.

Hence, pattern not matched here. Let's roll over to next sub-string which is 010

Hash value of 010 is:

6⁰ * 0 + 6¹ * 1 + 6² * 0 = 6 not equal to 43.

Hence, pattern not matched. Next sub-string: 011

hash value of 011 is:

6⁰ * 0 + 6¹ * 1 + 6² * 1 = 42 not equal to 43.

Next sub-string is- 001

hash value for 001 is:

6⁰ * 0 + 6¹ * 0 + 6² * 1 = 36 not equal to 43.

Next sub-string is : 110

hash value is :

6⁰ * 1 + 6¹ * 1 + 6² * 0 = 12 not equal 43.

On traversing the entire text the pattern is not found. This is the final result of the rabin-karp.