- #1

Sunwoo Bae

- 60

- 4

- 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!

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!