#boyermoore — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #boyermoore, aggregated by home.social.
-
Аудит алгоритмов: как реализация 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 #строковый_поиск