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

Дата публикации: 21-06-2026 19:12:28

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

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	HyperLogLog: как найти уникальные значения в терабайте данных, не храня их	0	7	24-06-2026
2	Из ядра Linux выпилили strncpy: шесть лет, 362 коммита, одна функция	0	8	23-06-2026
3	Как биология и особенности медицинского учета издеваются над программистами	0	5	24-06-2026
4	USB без магии: устройство протокола	0	7	23-06-2026
5	Как двое договариваются о секрете, крича на всю площадь: алгоритм Диффи-Хеллмана без формул	0	5	25-06-2026
6	Полвека с дипломом ИТ-шника. Дан приказ ему на Запад	0	5	22-06-2026
7	Бормашина — друг DIY-щика	5	6	21-06-2026
8	БумЗдРАвБаяре и Баярышъни-СамоДержавцы-СТОики¡¡¡👍👋👏🙏😇💥💯🔥⚡☀️💫🌟⭐	10	1	27-06-2026
9	[Перевод] Вынужден попрощаться: руководство Google окончательно утратило моральные принципы	-5	6	21-06-2026
10	Ну и пригодились тебе твои синусы?	0	5	20-06-2026

Классификация: . Схожих патентов: 0. Схожих новостей: 10. Тональность: 0. Информативность: 8. Источник: habr.com.