Эффективность встроенного метода поиска подстроки Python: find() против алгоритма Кнута-Морриса-Пратта

Аннотация

В статье проводится сравнительный анализ эффективности встроенного метода поиска подстрок str.find() в Python и алгоритма Кнута-Морриса-Пратта (КМП). Исследование выполнено в среде Google Colab с использованием Python 3.11.13. Экспериментальная часть включает генерацию тестовых данных различной длины, замер времени выполнения алгоритмов с помощью модуля timeit и визуализацию результатов. Результаты демонстрируют, что встроенный метод str.find() показывает более высокую производительность в большинстве сценариев, особенно при работе с короткими подстроками в длинных текстах. Алгоритм КМП, несмотря на теоретические преимущества, уступает по скорости из-за накладных расходов на вычисление префикс-функции. Работа содержит практические рекомендации по выбору оптимального метода поиска подстрок в зависимости от специфики задачи.