Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

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

index = -1 for i in xrange(len(haystack)-len(needle)+1):     success = True     for j in xrange(len(needle)):         if needle[j]<>haystack[i+j]:             success = False             break     if success:         index = i         break print index 

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае. Прежде чем перейти к описанию алгоритма, необходимо рассмотреть понятие префикс-функции.

Префикс-функция строки π(S,i) – это длина наибольшего префикса строки S[1..i], который не совпадает с этой строкой и одновременно является ее суффиксом. Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. Для строки S удобно представлять префикс функцию в виде вектора длиной |S|-1. Можно рассматривать префикс-функцию длины |S|, положив π(S,1)=0. Пример префикс функции для строки «abcdabcabcdabcdab»:

S[i]	a	b	c	d	a	b	c	a	b	c	d	a	b	c	d	a	b
π(S,i)	0	0	0	0	1	2	3	1	2	3	4	5	6	7	4	5	6

Предположим, что π(S,i)=k. Отметим следующие свойства префикс-функции.

1. Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
2. S[1..π(S,k)] является суффиксом строки S[1..i]. Действительно, если строка S[1..i] оканчивается строкой S[1… π(S,i)]=S[1..k], а строка S[1..k] оканчивается строкой S[1..π(S,k)], то и строка S[1..i] оканчивается строкой S[1..π(S,k)].
3. ∀ j∈(k,i), S[1..j] не является суффиксом строки S[1..i]. В противном случае было бы неверным предположение π(S,i)=k, так как j>k.

Рассмотренные свойства позволяют получить алгоритм алгоритм вычисления префикс-функции.
Пусть π(S,i)=k. Необходимо вычислить π(S,i+1).

1. Если S[i+1]=S[k+1], то π(S,i+1)=k+1.
2. Иначе, если k=0, то π(S,i+1)=0.
3. Иначе положить k:=π(S,i) и перейти к шагу 1.

Ключевым моментом для понимания сути алгоритма является тот факт, что если найденный на предыдущем шаге суффикс не может быть расширен на следующую позицию, то мы пытаемся рассматривать меньшие суффиксы до тех пор, пока это возможно.

Алгоритм вычисления префикс-функции на языке Python:

def prefix(s):     v = [0]*len(s)     i = 1     for i in xrange(1,len(s)):         k = v[i-1]         while k > 0 and s[k] <> s[i]:             k = v[k-1]         if s[k] == s[i]:             k = k + 1         v[i] = k     return v 

Покажем, что время работы алгоритма составляет О(n), где n=|S|. Заметим, что асимптотику алгоритма определяет итоговое количество итераций цикла while. Это так, поскольку без учета цикла while каждая итерация цикла for выполняется за время, не превышающее константу. На каждой итерации цикла for k увеличивается не более чем на единицу, значит максимально возможное значение k=n–1. Поскольку внутри цикла while значение k лишь уменьшается, получается, что k не может суммарно уменьшиться больше, чем n–1 раз. Значит цикл while в итоге выполнится не более n раз, что дает итоговую оценку времени алгоритма O(n).

Рассмотрим алгоритм Кнута-Морриса-Пратта, основанный на использовании префикс-функции. Как и в примитивном алгоритме поиска подстроки, образец «перемещается» по строке слева направо с целью обнаружения совпадения. Однако ключевым отличием является то, что при помощи префикс-функции мы можем избежать заведомо бесполезных сдвигов.

Пусть S[0..m–1] – образец, T[0..n–1] – строка, в которой ведется поиск. Рассмотрим сравнение строк на позиции i, то есть образец S[0..m–1] сопоставляется с частью строки T[i..i+m–1]. Предположим, первое несовпадение произошло между символами S[j] и T[i+j], где i < j < m. Обозначим P = S[0..j–1] = T[i..i+j–1]. При сдвиге можно ожидать, что префикс S сойдется с каким-либо суффиксом строки P. Поскольку длина наиболее длинного префикса, являющегося одновременно суффиксом, есть префикс-функция от строки S для индекса j, приходим к следующему алгоритму:

1. Построить префикс-функцию образца S, обозначим ее F.
2. Положить k = 0, i = 0.
3. Сравнить символы S[k] и T[i]. Если символы равны, увеличить k на 1. Если при этом k стало равно длине образца, то вхождение образца S в строку T найдено, индекс вхождения равен i – |S| + 1. Алгоритм завершается. Если символы не равны, используем префикс-функцию для оптимизации сдвигов. Пока k > 0, присвоим k = F[k–1] и перейдем в начало шага 3.
4. Пока i < |T|, увеличиваем i на 1 и переходим в шаг 3.

Возможная реализация алгоритма Кнута-Морриса-Пратта на языке Python выглядит так:

def kmp(s,t):     index = -1     f = prefix(s)     k = 0     for i in xrange(len(t)):         while k > 0 and s[k] <> t[i]:             k = f[k-1]         if s[k] == t[i]:             k = k + 1         if k == len(s):             index = i - len(s) + 1             break     return index