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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Постановка задачи[править | править вики-текст]

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

Идея[править | править вики-текст]

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

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

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

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

Описание алгоритма и оценка времени работы[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
  2. Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). «Fast pattern matching in strings». SIAM Journal on Computing 6 (2): 323–350. DOI:10.1137/0206024.

Ссылки[править | править вики-текст]