Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 18 - Строки. Поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта

Определения:
строка - последовательность символов.
подстрока - последовательность подряд идущих символов в строке.
префикс - подстрока, начинающаяся с первого символа строки.
суффукс - подстрока, заканчивающаяся на последний символ строки.

Обозначение
Будем говорить, что алгоритм работает за время O(f(N)) (или имеет сложность O(f(N))), если существует константа C, не зависящая от N такая, что данный алгоритм выполняется не более чем за C*f(N) операций. Здесь N - некоторая величина, характеризующая входные данные. Например, при оценке времени работы алгоритмов сортировки берут N - длину сортируемого массива. Иногда входные данные удобно описывать несколькими переменными (например, для алгоритмов на графах - это количество вершин и ребер в графе). Тогда функция f будет зависеть от нескольких переменных - f(V,E).

Формулировка задачи

Пусть есть две строки S и T, требуется найти все (первое) вхождения строки T в строку S. Будем считать, что длина строки S - N, а T - M символов.

Пример: S = "aabaababa" T = "aaba" вхождения будут в начиная с 1-го и 4-го символов строки S.

Простейший алгоритм

Простейший алгоритм перебирает все позиции строки S и смотрит, не входит ли T в S, начиная с этой позиции.

	for i := 1 to length(S) do begin
	  substring := true;
	  for j := 1 to length(T) do
	    if (S[i] <> T[j]) then
	      substring := false;
	  if substring then
	    //добавляем в список вхождений
	end;    

Как видно, алгоритм очень простой, но неэффективный, его сложность равна O(N*M).

Алгоритм Кнута-Морриса-Пратта

Для начала введем понятие префикс-функции.
Обозначим P(s) - длину маскимального префикса строки s, являющегося суффиксом s, при этом не совпадающим с s. Префикс-функция определена на множестве префиксов строки S и равна P(x), где х - префикс.

Предположим, что мы можем построить префикс-функцию для любой строки за O(N), где N - длина строки. Тогда мы сможем выполнить поиск подстроки в строке за линейное время (т.е. за время O(N)).
Действительно, возьмем строку T$S ($ - символ, которого нет ни в одной из строк) и построим для этой строки префикс-функцию. Если где-то префикс-функция равна M (длина строки T), это значит, что в этом месте заканчивается вхождение T в S (т.к. префикс строки T$S длины M есть T).

Теперь приведем алгоритм построения префикс-функции за линейное время.
Предположим, что мы уже построили префикс-функцию для первых K символов, тогда для вычисления следующего значения нам надо просмотреть все префиксы, являющиеся суффиксами слова из первых K символов, проверив, можно ли к ним "дописать" один символ так, чтобы он стал префиксом и суффиксом слова длины K+1, и выбрать среди них максимальный.
Заметим, что максимальный префикс, являющийся суфиксом слова длины K есть просто значение префикс-функции для K, второй по максимальности - значение префикс-функции от этого максимального префикса, и так далее. Тем самым мы нашли способ, как перебрать все префикс-суффиксы.
Ниже приведен код для построения префикс-функции от строки.

	p[1] := 0;
	k := 0;
	for i := 2 to N do
	  while (k > 0) and (s[p[k] + 1] <> s[i]) do begin
	    k := p[k];
	    if (s[p[k] + 1] = s[i]) then begin
	      inc(k);
	      p[i] := k;
	      break;
	    end;	    
	  end;

Заметим, что для поиска подстроки в строке нам не нужно в явном виде создавать строку T$S. Достаточно посчитать префикс-функцию для T, и на ее основе - префикс-функцию для S.