Question

When working modulo q = 17, how many spurious hits does the Rabin-Karp matcher
encounter in the text T = 29103292566473 when looking for the pattern 22?

Answer 1

Here to implement Robin Karp algo, we have to generate a hash for each substring we compare. We first generate a hash for pattern string and then iterate through the array comparing the hash with other sub strings.

For generating Hash, we replace the given string with ascii value and multiply with corresponding 10 value(start multiplying from right hand side as 10^0, then 10^1 and so on).........

In This case, we get 2 matches ie. 56 and 73.

Please feel free to Revert back for any queries

の) --T- 29-10-3 292 5 664千3 1 + pattern=22 13

Date Page No - visit us at www.aerolineproducts.com 1 6 29-2-13 시。 IH