#️⃣ Рабін–Карп
Пошук рядка через ковзний хеш
Початок вікна 0 / 0
Знайдено збігів: 0
Налаштування
Керування
Статистика
Початок вікна
0
Хеш вікна
0
Хеш шаблону
0
Порівнянь
0
Журнал збігів
Інформація та теорія

Рабін–Карп знаходить входження шаблону довжиною m усередині тексту довжиною n, пересуваючи вікно розміром m уздовж тексту та порівнюючи числовий відбиток — хеш — вікна з хешем шаблону, замість того щоб порівнювати символи безпосередньо на кожній позиції.

Поліноміальний ковзний хеш

Кожне вікно символів c₀ c₁ … c(m−1) розглядається як цифри числа в системі числення з основою b:

  • h = (c₀·b^(m−1) + c₁·b^(m−2) + … + c(m−1)) mod p
  • b — основа (наприклад, 256), p — велике просте число (наприклад, 1 000 000 007), яке обмежує хеш і зменшує кількість колізій.

Зсув за O(1)

Перерахунок хешу з нуля на кожній позиції коштував би O(m) на зсув. Натомість Рабін–Карп оновлює його інкрементально: видаляє внесок символу, що виходить із вікна, зсуває решту цифр на одну позицію та додає символ, що входить — h′ = ((h − text[i]·b^(m−1))·b + text[i+m]) mod p, додаючи p перед фінальним mod щоразу, коли віднімання дає від'ємне число. Це коштує O(1) на зсув незалежно від m.

Чому потрібна перевірка після збігу хешів

Різні вікна іноді можуть збігатися за значенням хешу, навіть якщо їхні символи відрізняються — хибне спрацювання. Щоразу, коли хеш вікна дорівнює хешу шаблону, Рабін–Карп виконує явне посимвольне порівняння, щоб підтвердити справжній збіг перед його повідомленням, гарантуючи коректність незалежно від колізій.

Складність

Середній і типовий час роботи становить O(n + m), оскільки перевірка запускається лише при (рідкісних) збігах хешів. Найгірший випадок — O(n·m), якщо багато хибних спрацювань змушують виконувати повторні повні перевірки — вкрай малоймовірно з великим простим модулем, але це можна продемонструвати тут за допомогою опції малого модуля. Ідея хешування Рабіна–Карпа також природно узагальнюється на пошук кількох шаблонів одночасно за один прохід, чого однопатернові алгоритми не можуть зробити так само дешево.

Про алгоритм Рабіна–Карпа

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Алгоритм Рабіна–Карпа, опублікований Майклом О. Рабіном і Річардом М. Карпом у 1987 році, шукає шаблон довжиною m усередині тексту довжиною n, використовуючи поліноміальний ковзний хеш замість порівняння символів на кожній позиції. Хеш першого вікна обчислюється безпосередньо, а хеш кожного наступного вікна виводиться з попереднього за постійний час, віднімаючи внесок символу, що виходить, зсуваючи залишок і додаючи символ, що входить, — усе за великим простим модулем. Оскільки обчислення та зсув хешу коштують O(1), алгоритм сканує весь текст за O(n), переходячи до посимвольної перевірки O(m) лише тоді, коли хеш вікна збігається з хешем шаблону — рідкісна подія при добре обраному модулі, але необхідна, щоб виключити колізії хешів, або "хибні спрацювання". Цей прийом хешування також елегантно узагальнюється на пошук багатьох шаблонів одночасно за один прохід — завдання, з яким інші однопатернові алгоритми пошуку рядків справляються менш ефективно.

Поширені запитання

Для чого використовується алгоритм Рабіна–Карпа?

Рабін–Карп шукає один або кілька шаблонів усередині більшого тексту, порівнюючи значення хешів замість необроблених символів на кожній позиції. Він особливо добре підходить для виявлення кількох шаблонів одночасно (хешуючи всі їх і перевіряючи ковзний хеш тексту проти набору) і є основним будівельним блоком інструментів виявлення плагіату та деяких реалізацій утиліт сімейства Unix `diff`.

Чому збіг хешів усе одно потребує перевірки символів?

Хеш стискає багато можливих рядків у число фіксованого розміру, тож два справді різні підрядки іноді можуть відображатися на те саме значення хешу — колізія. Рабін–Карп трактує збіг хешу лише як кандидата і завжди перевіряє фактичні символи перед підтвердженням збігу, що гарантує коректність, хоча саме лише хешування цього не може забезпечити.

Яка часова складність алгоритму Рабіна–Карпа?

За хорошого модуля середня й типова складність становить O(n + m): кожен із n − m + 1 зсувів вікна коштує O(1) для оновлення хешу, а перевірка виконується лише при рідкісних збігах хешів. Теоретичний найгірший випадок — O(n·m), що трапляється лише якщо ворожий вхід або поганий модуль спричиняють перевірку майже на кожному вікні.

Як Рабін–Карп порівнюється з KMP чи наївним пошуком?

Наївний пошук порівнює символи з нуля на кожній позиції, коштуючи O(n·m) у найгіршому випадку. KMP гарантує O(n + m) у найгіршому випадку, використовуючи попередньо обчислену функцію відмови, але лише для одного шаблону. Рабін–Карп відповідає середній швидкості KMP, водночас природно розширюючись на пошук багатьох шаблонів одночасно, що зазвичай і робить його кращим вибором на практиці.