Algorytmy i struktury danych · Senior · Pytanie 21 z 75
Jaka jest kluczowa idea wyszukiwania wzorca Rabina-Karpa?
- ✓Poprawna odpowiedź: Hasz kroczący porównuje wzorzec z każdym oknem w O(1)
- 2Przeskakuje do przodu według ostatniego znaku wzorca
- 3Buduje trie ze wszystkich sufiksów tekstu
Wyjaśnienie
Gdy okno przesuwa się o znak, hasz jest aktualizowany: stary znak usuwany, nowy dodawany. Znak po znaku porównuje się tylko okna z pasującym haszem. Błyszczy przy szukaniu wielu wzorców naraz.