Поиск подстроки в строке

Поиск подстроки в строке (англ. String searching algorithm) — класс алгоритмов над строками, которые позволяют найти паттерн (needle) в тексте (haystack).

Классификация алгоритмов поиска подстроки в строке

Сравнение — «чёрный ящик»

Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.

Преимущества:

• позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.

Недостатки:

• не выдается точка, в которой произошло несовпадение.

По порядку сравнения паттерна в тексте

Прямой

Преимущества:

• отсутствие регрессии на «плохих» данных.

Недостатки:

• не самая хорошая средняя асимптотическая сложность.

Обратный

Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.

Преимущества:

• при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов.

Недостатки:

• производительность сильно зависит от данных.

Сравнение в необычном порядке

Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.

По количеству поисковых шаблонов

Сколько поисковых шаблонов может обработать алгоритм за один раз.

• один шаблон (англ. single pattern algorithms)
• конечное количество шаблонов (англ. finite set of patterns)
• бесконечное количество шаблонов (англ. infinite number of patterns) (см. Теория формальных языков)

По необходимости препроцессинга текста

Виды препроцессинга:

• Префикс-функция
• Z-функция
• Бор
• Суффиксный массив

Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.

Сравнение алгоритмов

• $|\Sigma| = \sigma$­ — размер алфавита
• $|text| = t$ — длина текста
• $|pattern| = p$ — длина паттерна
• $a$ — размер ответа(кол-во пар)
• $m$ — суммарная длина всех паттернов

Название	Среднее	Худшее	Препроцессинг	Дополнительная память	Кол-во поисковых шаблонов	Порядок сравнения	Описание
Наивный алгоритм (Brute Force algorithm)	$O(p \cdot (t - p))$	$O(p^2)$		$O(1)$	Single	Прямой	Сравнение — «чёрный ящик». Если $p$ достаточно мало по сравнению с $t$, то асимптотика будет близкой к $O(t)$, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
Поиск подстроки в строке с помощью Z-функции	$O(t)$	$O(t)$	$O(p + t)$	$O(p)$	Single	Прямой
Алгоритм Рабина-Карпа (Karp-Rabin algorithm)	$O(p + t)$	$O(pt)$	$O(p)$	$O(1)$	Single / Finite	Прямой	Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
Алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt algorith)	$O(p + t)$	$O(p + t)$	$O(p)$	$O(p)$	Single	Прямой	Использует префикс-функцию
Алгоритм Колусси (Colussi algorithm)	$O(t)$	$O(t)$	$O(p)$	$O(p)$	Single	Прямой / Обратный	Оптимизация Алгоритма Кнута-Морриса-Пратта использует как прямой, так и обратный обход
Алгоритм Ахо-Корасик (Aho–Corasick string matching algorithm)	$O(m + t + a)$	$O(t)$	$O(m)$	$O(m\sigma)$	Finite	Прямой	Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как Красно-черное дерево. В последнем случае уменьшится расход памяти, но ухудшится асимптотика
Алгоритм Shift-Or	$O(t)$	$O(t \cdot \dfrac{n}{w})$ $w$ — размер машинного слова	$O(p + \sigma)$	$O(p + \sigma)$	Single	Прямой	Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если $p \leqslant w$. Иначе деградирует и по памяти, и по сложности
Алгоритм Бойера-Мура (Boyer-Moore algorithm)	$O(t)$	$O(pt)$	$O(p + \sigma)$	$O(p + \sigma)$	Single	Обратный	Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций
Поиск подстроки в строке с помощью суффиксного массива (Suffix array)	$O(p\log t)$	$O(p\log t)$	$O(t)$	$O(t)$	Single	Прямой	Использует Суффиксный массив. Если использовать Largest common prefix (lcp), то можно уменьшить асимптотику до $O(p + \log t)$. Суффиксный массив можно строить стандартными способами или алгоритмом Каркайнена-Сандерса. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Каркайнена-Сандерса
Поиск подстроки в строке с помощью суффиксного дерева (Suffix tree)	$O(p)$	$O(p)$	$O(t)$	$O(t)$	Single	Прямой	Позволяет выполнять поиск подстроки в строке за линейное время

Источники информации

• Википедия — Поиск подстроки
• Википедия — String searching algorithm
• ESMAJ — (англ.) Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.