Аудит алгоритмов: как реализация Boyer-Moore с 190K звёзд на GitHub оказалась brute-force

Проверил реализацию Boyer-Moore в TheAlgorithms/Python (190K+ звёзд). Оказалось, что сдвиг bad character записывается в переменную for-цикла, что в Python не имеет эффекта. Алгоритм выдаёт правильные результаты, но работает как brute-force O(nm) вместо O(n/m). Плюс ещё две находки: бесконечный цикл в типичных реализациях full BM и ошибка в оригинальной статье 1977 года, которую исправили только в 1980-м.

https://habr.com/ru/articles/1050180/

#алгоритмы #BoyerMoore #Python #тестирование #баги #open_source #propertybased_testing #строковый_поиск