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

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как 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,k) и перейти к шагу 1.


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

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

def prefix(s):
    v = [0]*len(s)
    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
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 16

    +1
    Зачем публиковать алгоритм, реализации которого уже сотни раз выкладывались в Интернет?
      +6
      Вероятно интересует не сама реализация, а его разъяснение? Как если понимаешь математику/физику, любую формулу можно вывести самому
        +2
        Интерес представляет именно вывод алгоритма и его разъяснение.
        0
        Надо заметить, что на практике обычно КМП в два раза медленнее своего наивного аналога. Дело в накладных расходах, константа в оценке сложности A*n велика, тогда как среднее время работы наивного алгоритма составляет всего 2*n, что легко показать и далеко от худшей оценки. Расскажите лучше про алгоритм Хорспулла: сам алгоритм простой, а вот вывод оценки сложности нетривиален.
          +3
          На практике классические алгоритмы CS вообще редко применяются :) Это, конечно, провокационное утверждение, но у любой прикладной задачи, как правило, присутствует более простое, быстрое и менее универсальное решение, которое отлично подходит для нужд потребителя.

          КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за O(n) универсально, без использование `читов` вроде хэширования, предположений о размере алфавита, свойствах строки и т.д.

          Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.
            +1
            Можете привести вывод среднего времени работы наивного алгоритма?
            0
            Статья неплохая, но позволю себе высказать пару замечаний. При определении префиксной функции используется формальное определение с небольшим пояснением, оба они читаются очень тяжело. Вот тут, к примеру, к этому добавлено текстовое описание того, что означают элементы посчитанной префиксной функции, это очень помогает понять её суть. Потому что об формальное определение (и о пояснение) можно мозг сломать. То же самое можно сказать и о дальнейшем описании уже сути алгоритма. По приведённой выше ссылке всё понятно, а здесь, увы, нет. Это касается и свойств префиксной функции, и собственно алгоритма.
              0
              «Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. „
              Мне кажется, это интуитивно понятное определение. Плюс табличка служит примером.
              0
              В первом листинге переменные имеют «человеческие» имена. И код читается очень легко. Остальные читать тяжело.
              Я понимаю, что у Кормена алгоритмы описаны аналогично, но зачем же вносить эту ненужную сложность?
                +1
                Первый листинг читается сложнее, чем следующие — глаз вязнет в длинных именах, трудно увидеть логику.
                  +1
                  Разные подходы :)
                    0
                    Разные привычки :D
                +1
                А зачем в следующем фрагменте «i=1»? В этом есть смысл? Или просто невнимательность?
                def prefix(s):
                    v = [0]*len(s)
                    i = 1
                    for i in xrange(1,len(s)):
                        k = v[i-1]
                        ...
                
                  0
                  Это невнимательность. Убрал.
                  +2
                  Откройте для себя возможность создавать else к циклам типа for в Python. Примитивный алгоритм можно записать без дополнительной переменной success:
                  index = -1
                  for i in xrange(len(haystack)-len(needle)+1):
                      for j in xrange(len(needle)):
                          if needle[j]<>haystack[i+j]:
                              break
                      else:
                          index = i
                          break
                  print index
                  
                    0
                    Спасибо, удобная конструкция.

                  Only users with full accounts can post comments. Log in, please.