Алгоритм Рабіна - Карпа - це алгоритм пошуку рядка, який шукає шаблон, тобто підрядок, в тексті використовуючи хешування. Він був розроблений в 1987 році Майклом Рабіном і Річардом Карпом.
Алгоритм має значну теоретичну важливість, дуже ефективний у пошуку збігів множинних шаблонів. Для тексту довжини n і шаблона довжини m, його середній час виконання та кращий час виконання це O (n), але в гіршому випадку він має продуктивність O (nm). Проте, алгоритм має унікальну особливість знаходити будь-яку з k рядків менш, ніж за час O (n) в середньому, незалежно від розміру k.
Одне з найпростіших практичних застосувань алгоритму Рабіна - Карпа полягає у визначенні плагіату. Скажімо, наприклад, що студент пише роботу з Мобі Діку. Професор знаходить різні вихідні джерела по Мобі Діку і автоматично витягує список речень з цих джерел. Потім, алгоритм Рабіна - Карпа може швидко знайти у перевіреній статті приклади входження деяких речень з вихідних джерел. Для усунення чутливості алгоритму до невеликих відмінностей, можна ігнорувати деталі, такі як регістр або пунктуація за допомогою їх видалення.

Алгоритм Рабіна - Карпа - це алгоритм пошуку рядка, який шукає шаблон, тобто підрядок, в тексті використовуючи хешування. Він був розроблений в 1987 році Майклом Рабіном і Річардом Карпом. Алгорит...