Rabin- Karp - Codeforces

→ Обратите внимание

До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя HekpoMaH

Rabin- Karp

Автор HekpoMaH, 11 лет назад, По-английски

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!!!

rabin- karp algo

-6

HekpoMaH
11 лет назад
9

Комментарии (7)

Показать архивные | Написать комментарий?

yeputons

11 лет назад, # |

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.

→ Ответить

HolyInq

11 лет назад, # ^ |

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.

→ Ответить

yeputons

11 лет назад, # ^ |

← Rev. 2 →

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 10⁵ patterns: a, aa, ..., aaa...aaa and text is aaa...aaa, we have about 10¹⁰ 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 $\text{[math]}$ different lengths and problem can be solved in $\text{[math]}$ (L is a length of the text).