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

Даны образец (строка) ${\displaystyle \displaystyle S}$ и строка ${\displaystyle \displaystyle T}$. Требуется определить индекс, начиная с которого образец ${\displaystyle \displaystyle S}$ содержится в строке ${\displaystyle \displaystyle T}$. Если ${\displaystyle \displaystyle S}$ не содержится в ${\displaystyle \displaystyle T}$ — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.

Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.

если haystack[i] = needle[state]
  то state = state + 1
  иначе state = побочный_переход(state, haystack[i])

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

Рассмотрим сравнение строк на позиции ${\displaystyle \displaystyle i}$, где образец ${\displaystyle \displaystyle S[0,m-1]}$ сопоставляется с частью текста ${\displaystyle \displaystyle \displaystyle T[i,i+m-1]}$. Предположим, что первое несовпадение произошло между ${\displaystyle \displaystyle \displaystyle T[i+j]}$ и ${\displaystyle \displaystyle S[j]}$, где ${\displaystyle \displaystyle 1<j<m}$. Тогда ${\displaystyle \displaystyle T[i,i+j-1]=S[0,j-1]=P}$ и ${\displaystyle \displaystyle a=T[i+j]\neq S[j]=b}$.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца ${\displaystyle \displaystyle S}$ сойдется с каким-нибудь суффиксом (конечные символы) текста ${\displaystyle \displaystyle P}$. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки ${\displaystyle \displaystyle S}$ для индекса ${\displaystyle \displaystyle j}$.

Это приводит нас к следующему алгоритму: пусть ${\displaystyle \displaystyle {\rm {{\pi }[j]}}}$ — значение префикс-функции от строки ${\displaystyle \displaystyle S[0,m-1]}$ для индекса ${\displaystyle \displaystyle j}$. Тогда после сдвига мы можем возобновить сравнения с места ${\displaystyle \displaystyle T[i+j]}$ и ${\displaystyle \displaystyle S[{\rm {{\pi }[j]]}}}$ без потери возможного местонахождения образца. Можно показать, что таблица ${\displaystyle \displaystyle {\rm {\pi }}}$ может быть вычислена (амортизационно) за ${\displaystyle \displaystyle \Theta (m)}$ сравнений перед началом поиска. А поскольку строка ${\displaystyle \displaystyle T}$ будет пройдена ровно один раз, суммарное время работы алгоритма будет равно ${\displaystyle \displaystyle \Theta (m+n)}$, где ${\displaystyle n}$ — длина текста ${\displaystyle \displaystyle T}$.

function KMP(S, T) 
  k ← 0
  A ← ø   // A - пустое множество
  π ← Prefix_Function(S)    // считается префикс-функция от образца S
  for i = 1 to |T| do    // |T| - длина строки T
    while k > 0 and T[i] ≠ S[k + 1] do
      k ←  π[k]
    end while
    if T[i] = S[k + 1] then
      k ← k + 1
    end if
    if k = |S| then
      A ← A ⋃ {i - |S| + 1} // это если мы в начале считали префикс-функцию
      A ← A ⋃ {i}           // это если мы в начале считали z-функцию
      k ← π[k]
    end if
  end for
  return A  
end function

Функция возвращает ${\displaystyle \displaystyle A}$ — множество номеров элементов строки ${\displaystyle \displaystyle T}$, которыми оканчиваются найденные вхождения ${\displaystyle \displaystyle S}$ в ${\displaystyle \displaystyle T}$.