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.

  • $\begingroup$ 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. $\endgroup$
    – Louis
    Commented Mar 1, 2013 at 16:40
  • $\begingroup$ Perhaps the Handbook of exact string matching algorithms helps. $\endgroup$
    – uli
    Commented Mar 1, 2013 at 18:32
  • 2
    $\begingroup$ how about the wikipedia entry on said algorithm? $\endgroup$
    – didierc
    Commented Mar 3, 2013 at 1:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.