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!!!
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.
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.
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 isaaa...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).Video
Theoretical explanation and implementation here.
Can anyone please share a tested code they use in contests ?
Link Codeforces Round #166 (Div. 2) D. Good Substrings Link on task