В 2015 году группа исследователей (Flouri et al.) решила проверить реализации классического алгоритма Готоха (1982) для выравнивания биологических последовательностей. Из 10 проверенных реализаций только 2 давали правильный результат. 8 из 31 учебных материалов содержали математическую ошибку.
Я решил проверить, насколько это типично для других классических алгоритмов. Начал с Boyer-Moore (1977), одного из самых известных алгоритмов поиска подстроки.
Методология
Написал тестовый фреймворк, который проверяет любую реализацию поиска подстроки против brute-force эталона:
35 статических тестов: пустые строки, перекрывающиеся совпадения, периодические строки, pattern == text
Property-based случайные тесты (8000+ на реализацию): полнота (все совпадения найдены), корректность (нет ложных срабатываний), порядок, количество
Разные распределения: маленький/большой алфавит, бинарные строки, длинные паттерны
Находка 1: TheAlgorithms/Python (190K+ звёзд)
Самый популярный образовательный репозиторий алгоритмов на GitHub. Файл strings/boyer_moore_search.py.
Метод bad_character_heuristic() пытается использовать правило плохого символа для пропуска позиций. Но сдвиг записывается в переменную цикла for:
for i in range(self.textLen - self.patLen + 1): mismatch_index = self.mismatch_in_text(i) if mismatch_index == -1: positions.append(i) else: match_index = self.match_in_pattern(self.text[mismatch_index]) i = (mismatch_index - match_index) # мёртвый код
В Python переприсвоение переменной for-цикла не влияет на следующую итерацию. for i in range(N) всегда берёт следующее значение из range(), игнорируя любые изменения i внутри тела цикла.
Я добавил счётчик итераций:
Текст: 32 символа, Паттерн: 4 символа Итераций выполнено: 29 (= brute-force) Рабочий Boyer-Moore: ~8 итераций
Алгоритм выдаёт правильные результаты, поэтому все тесты проходят. Но работает за O(nm) вместо O(n/m). Каждый, кто скопировал этот код, думает что у него Boyer-Moore, а на самом деле имеет наивный поиск с лишними вычислениями.
Исправление тривиальное: заменить for на while.
Находка 2: бесконечный цикл при pattern == text
Типичная реализация полного Boyer-Moore (с обоими правилами: bad character + good suffix) зависает на тривиальном входе search("abc", "abc").
Причина: при полном совпадении индекс i декрементируется на m позиций (с m-1 до -1). Затем good_suffix[0] сдвигает i ровно на m назад. i возвращается на исходную позицию. Цикл бесконечен.
Находка 3: оригинальная статья 1977 года содержала ошибку
Boyer и Moore опубликовали алгоритм в 1977 году, но не включили корректный алгоритм вычисления таблицы good suffix (delta2). Первый правильный алгоритм дал Войцех Ритер (Rytter) в 1980 году, через 3 года.
Эта ошибка продолжает распространяться. В 2019 году Microsoft исправляла баги в std::boyer_moore_searcher (C++17 STL), связанные именно с отсутствием Rytter correction.
Масштаб проблемы
Это не уникальная ситуация. Классические алгоритмы копируются между учебниками, лекциями и GitHub-репозиториями без верификации. Ошибки в оригинальных статьях распространяются десятилетиями.
Я составил список из 35 алгоритмов в 6 категориях (биоинформатика, численные методы, графы, сортировки, строки, вычислительная геометрия) для систематического аудита. Следующая цель: BLAST (1990), самый используемый инструмент биоинформатики. Формального аудита его корректности не существует, несмотря на 35 лет использования.
Код
Тестовый фреймворк и все результаты: https://github.com/devladpopov/algorithm-autopsy
Issue в TheAlgorithms/Python: https://github.com/TheAlgorithms/Python/issues/14844
Если знаете о подобных багах в классических алгоритмах, буду рад обсудить.
Комментарии (21)
LinkToOS
21.06.2026 19:40В Python переприсвоение переменной for-цикла не влияет на следующую итерацию.
Вы не уточнили - в C и Java такая реализация работает корректно, или приводит к ошибкам? То есть здесь описан случай неаккуратного переложения кода на несовместимый язык, или вариант кода с изменением i в теле цикла заведомо недопустим, независимо от языка программирования?
wl2776
21.06.2026 19:40Вы не уточнили - в C и Java такая реализация работает корректно, или приводит к ошибкам?
Если цикл не range-based из современных стандартов, и типы простые (`int`, `float` и т.п.), то да, такая реализация работает корректно.
Запись `for (int i = 0; i < max_value; i++)` это по сути компактная запись `while`.
Я считаю плохой практикой изменение переменной цикла внутри тела for, т.к. слово for настойчиво подразумевает, что эта переменная будет меняться только в одном месте, после окончания тела.
Для range-based for loops из современного С++ изменение переменной внутри цикла тоже в ряде случаев приемлемая и корректная операция. Пример:
std::vector<int> vec = {1, 2, 3}; for (int& val : vec) { val *= 2; }
Rel1cto
21.06.2026 19:40В последнем примере вы не меняете переменную, по которой идёт перебор значений цикла. Меняете тот элемент вектора, на который она ссылается.
wl2776
21.06.2026 19:40Да, верно. Там неявно создаётся итератор по коллекции, к которому, как я понимаю, вообще из кода доступа нет. Т.е. описываемый хак вообще невозможен.
wl2776
21.06.2026 19:40Поправка.
Для корректности работы алгоритма нужно учесть `i++` в конце цикла.
Т.е. правильное переложение с питона на С будет таким (если уж извращаться :) )
for(int i=0; i < textLen - patLen + 1; i++) { mismatch_index = mismatch_in_text(i); if (mismatch_index == -1) { positions.push_back(i); } else { match_index = match_in_pattern(self.text[mismatch_index]); i = mismatch_index - match_index - 1; // после выхода из else будет ещё i++ } }
vep
21.06.2026 19:40Существующие статические анализаторы кода для python какую штуку не подсвечивают?
Dimmirslr
21.06.2026 19:40Количество звездочек на гитхабе вообще ничего не говорит о реальном качестве кода под капотом...
funca
Хорошая находка и лишнее подтверждение, что авторитеты тоже ошибаются.
Интересно, почему только issue без PR?
StudyQA Автор
Спасибо! PR не отправил намеренно: хотел сначала зафиксировать баг как есть, чтобы мейнтейнеры сами решили, какой фикс им ближе :) Там есть несколько вариантов: с одной стороны, можно переписать на while-цикл с корректным сдвигом. А с другой, например, можно взять каноническую реализацию Rytter (1980) или вообще заменить на Horspool, который проще и на практике не медленнее. Если issue не закроют в ближайшее время, отправлю PR с Horspool-вариантом.
Genius_Russian_Coders
Классный разбор. Присвоение переменной цикла в Python — недооценённая ловушка: for молча её перезаписывает на каждой итерации. Я ловил ровно то же самое при портировании Z-алгоритма — все тесты зелёные, а сложность O(n²). Property-based testing такие вещи вскрывает мгновенно.
CitizenOfDreams
Я не программист, но по-моему, изменение переменной цикла внутри цикла for - это грязный хак. Если ты пишешь "for i in range (5)", то нормальный человек, который потом будет разбираться в твоем коде, предположит, что ты хотел получить ровно пять циклов со значениями i=0, 1, 2, 3, 4.
А для переменной, которая может произвольно меняться в любой момент, есть цикл while.
randomsimplenumber
Переписали с Си на Питон похоже. Но странно, обычно в учебниках алгоритмы на паскале-подобном псевдоязыке, без сионистских хаков.
CitizenOfDreams
На Си я бы точно так же назвал это грязным хаком. Я бы так написал разве что на старом Бейсике, в котором нет WHILE - потому что иначе пришлось бы рисовать цикл вручную на GOTO, что еще хуже.
wl2776
Вряд ли, реализации очень сильно отличаются.
https://github.com/TheAlgorithms/C/blob/e5dad3fa8def3726ec850ca66a7f51521f8ad393/searching/pattern_search/boyer_moore_search.c
https://github.com/TheAlgorithms/Python/blob/master/strings/boyer_moore_search.py
Dimmirslr
Иногда завести подробный багрепорт полезнее. Пулл-реквесты могут мариновать месяцами, а ишью привлекает внимание комьюнити к проблеме