A Question about modulus R in Rabin Karp Algorithm

[Sunwoo Bae]

Homework Statement

n/a

Relevant Equations

n/a

Hello, I am learning trying to set up a code that searches for a certain pattern in the text by implementing Rabin-Karp Algorithm.
When setting up the Rabin Karp hash function, I have been told that I should set a value q in order to lower the time complexity of the function, and that q should be a prime number that is larger than the length of the pattern that I want to find in the text.

1) Why exactly is it that the time complexity of the function is reduced when mod q is performed?
2) How do you determine the optimal prime number for q? Can it be any prime number that is bigger than the pattern length? For instance, if the pattern length is 3, what would be an optimal prime number?
3)Will value of q affect the time complexity of code in any way?

Thank you for your help!

 

[Valkarie]

1) Mod q is performed to reduce the time complexity of the Rabin Karp hash function. This works because when mod q is applied, the hash value of the pattern will be a much smaller number than the actual length of the pattern. This means that when the hash values of the text and the pattern are compared, the comparison can be done much faster since it is comparing much smaller numbers. 2) The optimal prime number for q is determined by the length of the pattern. Any prime number larger than the length of the pattern is suitable. For instance, if the pattern length is 3, the optimal prime number for q could be 5, 11, 17, etc. 3) Yes, the value of q will affect the time complexity of the code. A larger prime number for q will result in a slower search, whereas a smaller prime number for q will result in a faster search.