Алгоритми та структури даних · Senior · Запитання 21 з 75
Яка ключова ідея пошуку підрядка Рабіна-Карпа?
- ✓Правильна відповідь: Ковзний хеш порівнює шаблон із кожним вікном за O(1)
- 2Він перестрибує вперед за останнім символом шаблону
- 3Він будує trie з усіх суфіксів тексту
Пояснення
Коли вікно зсувається на символ, хеш оновлюється: старий символ прибирається, новий додається. Посимвольно порівнюються лише вікна з однаковим хешем. Він особливо добрий, коли шукають багато шаблонів одразу.