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

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

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

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

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

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

[math]-[/math] Не выдается точка, в которой произошло несовпадение.

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

Прямой

[math]+[/math] Отсутсвие регрессии на «плохих» данных.

[math]-[/math] Не самая хорошая средняя асимптотическая сложность.

Обратный

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

[math]+[/math] При несовпадении позволяет перемещать паттерн по строке сразу на несколько символов

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

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

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

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

1. Один шаблон (Single pattern algorithms)
2. Конечное количество шаблонов (finite set of patterns)
3. Бесконечное количество шаблонов (infinite number of patterns) (см. Теория формальных языков)

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

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

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

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

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

• [math]|\Sigma| = \sigma[/math]­ — размер алфавита
• [math]|haystack| = h[/math] — длина текста
• [math]|needle| = n[/math] — длина паттерна
• [math]a[/math] — размер ответа(кол-во пар)
• [math]m[/math] — суммарная длина всех паттернов

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

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

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