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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.