HekpoMaH's blog

Rabin- Karp
By HekpoMaH, 11 years ago, In English

Hi. I recently heard about Rabin- Karp algorithm and I know that it works in O(n+k) time, if we have n- sized text and k patterns to search for. The problem is the following- I don't know the algo, but I know hashing. Can you tell it to me? Can you give a source for example? Thank you for your attention!!!

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Main idea is polynomial hashing. Then we can easily calculate hash of any substring of the text in O(1) with O(n) precalculation. After that we try all the positions where pattern can start.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't we have multiple patterns?
    I know there is solution with hash table, when all pattern of same size. And after googling found that it's "obvious" to expand such solution on any patterns, but have no idea how to acheive it.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I prefer determenistic algorithms and the only modification of Rabin-Karp I know is the one that works with one pattern only.

      No idea how can we 'obviously' extend it to multiple patterns. For example, if we have 105 patterns: a, aa, ..., aaa...aaa and text is aaa...aaa, we have about 1010 matchings. So, we need to process them in blocks somehow. For example, we can group them by length: if summary length of patterns is S, then we have no more than different lengths and problem can be solved in (L is a length of the text).

      → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Video

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Theoretical explanation and implementation here.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please share a tested code they use in contests ?

→ Reply