# Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. Specifically, when the authors start proposing about some modulo operations for solving some problem, I am unable to follow. To be precise, the paragraphs from

We have intentionally overlooked one problem: p and ts may be too large too work with conveniently...

on till equation 32.2 (pp 991 in 3rd edition) are the paragraphs I am having problems with.

What does "convenient" mean here? Why do they use modulo? I am totally lost. Is it possible to explain this in simple english?

I will appreciate if someone can help me in understanding this paragraph. And if there is any other reference (with similar mathematical treatment) where this can be read, please tell me.

• This question would be better if you described the algorithm. IIRC, you pick a linear function mod $p$ and then go left to right computing fingerprints. If this is right, the point is that $p$ has to grow with $n$, so arithmetic isn't $O(1)$ per operation. Commented Mar 1, 2013 at 16:40
• Perhaps the Handbook of exact string matching algorithms helps.
– uli
Commented Mar 1, 2013 at 18:32
• how about the wikipedia entry on said algorithm? Commented Mar 3, 2013 at 1:22