Двоичный алгоритм поиска подстроки

Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск. Вычислительная сложность — O(|needle|·|haystack|) операций с крайне малой константой. На предварительную обработку идёт O(|needle|·|Σ|) операций и памяти, где Σ — алфавит. Если же длина шаблона поиска (в символах) не превышает длину машинного слова (в битах), сложность получается O(|haystack|) и O(|needle|+|Σ|) соответственно. Предполагается, что алгоритм разработал в 1964 году венгр Балинт Дёмёльки. Но популярность он приобрёл в 1990-е годы благодаря работам чилийца Рикардо Баэса-Ятеса и уругвайца Гастона Гоннета. На двоичном алгоритме основана известная утилита приблизительного поиска <a href="/w/index.php?title=Agrep&action=edit&redlink=1" class="new" title="Agrep (страница отсутствует)">agrep</a>.