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

Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.

Вычислительная сложность — O(|needle|·|haystack|) операций с крайне малой константой. На предварительную обработку идёт O(|needle|·|Σ|) операций и памяти, где Σ — алфавит. Если же длина шаблона поиска (в символах) не превышает длину машинного слова (в битах), сложность получается O(|haystack|) и O(|needle|+|Σ|) соответственно.

Предполагается, что алгоритм разработал в 1964 году венгр Балинт Дёмёльки. Но популярность он приобрёл в 1990-е годы благодаря работам чилийца Рикардо Баэса-Ятеса и уругвайца Гастона Гоннета. На двоичном алгоритме основана известная утилита приблизительного поиска agrep.

Источник: Википедия