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!!!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | Petr | 145 |
| 9 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.05.2024 20:37:03 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
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:
different lengths and problem can be solved in 
(L is a length of the text).
a,aa, ...,aaa...aaaand 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 thanVideo
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