Bitap: алгоритм сопоставления строк, который стоит полюбить
Bitap: My favorite string matching algorithm
Bitap (или shift-and) — малоизвестный алгоритм поиска подстроки, эффективный для коротких шаблонов длиной меньше машинного слова. Автор выводит его шаг за шагом из наивного перебора: сначала переходит к потоковой обработке, затем упаковывает активные состояния в битсет и заменяет вложенные циклы парой битовых операций — сдвигом и маскированием. Алгоритм подкупает простотой и элегантностью, хотя асимптотически не превосходит наивный.
Хотя я также подробно изучал Boyer-Moore и KMP, мне требуется довольно много времени, чтобы вывести их с нуля, тогда как bitap очень легко выводится, поскольку для меня это просто наивный алгоритм, переодетый по-другому.