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

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, она чрезвычайно важна.

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). Также обозначим через Σ алфавит, на котором проводится поиск.

Несостоятельность примитивного алгоритма

Если считать, что строки нумеруются с 1, простейший алгоритм выглядит так.

for i=0...|haystack|-|needle|
  for j=1...|needle|
    if haystack[i+j]<>needle[j] 
      then goto 1
  output("Найдено: ", i+1)
  1:

Простейший алгоритм поиска даже в лучшем случае проводит |haystack|−|needle|+1 сравнение; если же есть много частичных совпадений, скорость снижается до O(|haystack|·|needle|).

Для чего нужно так много алгоритмов?

Программисту приходится выбирать нужный алгоритм в зависимости от таких факторов.

1. «Враждебность» пользователя. Другими словами: будет ли пользователь намеренно задавать данные, на которых алгоритм будет медленно работать? Существуют очень простые алгоритмы, оценка которых O(|haystack|·|needle|) в худшем случае, но на «обычных» данных количество сравнений намного меньше |haystack|. Только в 1990-е годы были созданы алгоритмы, дающие сложность O(|haystack|) в худшем случае и меньше |haystack| в среднем.
2. Архитектура процессора. Некоторые процессоры имеют автоинкрементные или SIMD-операции, которые позволяют быстро сравнить два участка ОЗУ (например, rep cmpsd на x86). На таких процессорах заманчиво применить алгоритм, который просто бы сравнивал needle с haystack — разумеется, не во всех позициях.
3. Размер алфавита. Многие алгоритмы (особенно основанные на сравнении с конца) имеют эвристики, связанные с несовпавшим символом. На больших алфавитах таблица символов будет занимать много памяти, на малых — соответствующая эвристика будет неэффективной.
4. Возможность проиндексировать haystack. Если таковая есть, поиск серьёзно ускорится.
5. Требуется ли одновременный поиск нескольких строк? Некоторые алгоритмы (например, алгоритм Ахо-Корасик) позволяют это.

Алгоритмы

Для сокращения обозначим:

• |Σ|=σ — размер алфавита.
• |haystack|=h — длина строки, в которой ведётся поиск.
• |needle|=n — длина шаблона поиска.

Основанные на сравнении с конца

Название	Предв. обработка	Сложность		Примечания
		типичная	макс.
Алгоритм Бойера-Мура	O(n+σ)	<h	O(hn)	Стандартный алгоритм поиска подстроки в строке
Алгоритм Чжу-Такаоки	O(n+σ²)	<h	O(hn)	Алгоритм Бойера-Мура, оптимизированный под короткие алфавиты
Турбо-алгоритм Бойера-Мура	O(n+σ)	<h	≤2h	Один из наиболее эффективных алгоритмов, не имеющих регрессии на «плохих» данных

Основанные на сравнении как «чёрном ящике»

Во всех этих алгоритмах сравнение строк является «чёрным ящиком». Это позволяет использовать стандартные функции сравнения участков памяти, зачастую оптимизированные на ассемблерном уровне под тот или иной процессор.

К этой категории относится и примитивный алгоритм поиска.

Название	Предв. обработка	Сложность		Примечания
		типичная	макс.
Примитивный алгоритм	Нет	≥h−n+1	O(hn)
Алгоритм Бойера-Мура-Хорспула	O(σ)	<h	O(hn)