WikiSort.ru - Не сортированное

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом^[1]. Результаты своей работы они опубликовали совместно в 1977 году^[2].

Постановка задачи

Даны образец (строка) ${\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}$ .

См. также

• Префикс-функция
• Z-функция
• Алгоритм Бойера — Мура
• Алгоритм Ахо — Корасик

Примечания

Ссылки

Имеется викиучебник по теме
«Примеры реализации алгоритма КМП»

• Алгоритм Кнута-Морриса-Пратта на сайте Algolist, перевод работы Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algorithm // Цикл лекций Exact String Matching Algorithms, Université de Rouen, 1997

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Проставив сноски, внести более точные указания на источники.