Порівняння ефективності алгоритмів пошуку підрядка

Огляд

Цей документ презентує порівняння трьох алгоритмів пошуку підрядка: Кнута-Морріса-Пратта (KMP), Боєра-Мура та Рабіна-Карпа. Ефективність цих алгоритмів була випробувана на двох різних текстах (Стаття 1 та Стаття 2) та двох типах підрядків: один, який дійсно існує у тексті, та інший — вигаданий. Продуктивність вимірювалась за допомогою модуля timeit Python.

Алгоритми, що тестувалися

• Алгоритм Кнута-Морріса-Пратта (KMP)
• Алгоритм Боєра-Мура
• Алгоритм Рабіна-Карпа

Результати тестів

Було записано наступні часи для кожного алгоритму при пошуку підрядків у двох статтях:

Стаття 1

• Алгоритм KMP: 0.002209374913945794 секунди
• Алгоритм Боєра-Мура: 0.0007304588798433542 секунди
• Алгоритм Рабіна-Карпа: 0.004171374952420592 секунди

Стаття 2

• Алгоритм KMP: 0.010540083050727844 секунди
• Алгоритм Боєра-Мура: 0.004332083044573665 секунди
• Алгоритм Рабіна-Карпа: 0.02908033295534551 секунди

Висновки

На основі отриманих даних:

• У Статті 1, алгоритм Боєра-Мура показав найкращі результати.
• У Статті 2, також алгоритм Боєра-Мура продемонстрував найкращу продуктивність.

Загалом, алгоритм Боєра-Мура виявився найефективнішим у пошуку підрядків у обох текстах. Він рекомендується для використання в аналогічних задачах пошуку підрядка через його високу продуктивність і надійність.