07.11.2020

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


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

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

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

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

Идея

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

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

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

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

Описание алгоритма и оценка времени работы

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

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

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

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

Похожие новости:

Произведение Громова

Произведение Громова
Произведение Громова — расстояние, на котором две геодезические стартующих в одной точке начинают существенно расходиться. Названо в честь Громова. Произведение Громова используется, в частности

Константа скорости реакции

Константа скорости реакции
Константа скорости реакции (удельная скорость реакции) — коэффициент пропорциональности k {displaystyle k} в кинетическом уравнении реакции. Так, реакция

Число Цайзеля

Число Цайзеля
Число Цайзеля — свободное от квадратов число k {displaystyle k} , имеющее как минимум три простых делителя, для которых выполняется условие:

Функция Гёделя

Функция Гёделя
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел. Определение Функцией Геделя Γ ( x
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Жилой квартал Лесопарковый в Челябинске: отличительные особенности
Жилой квартал Лесопарковый в Челябинске: отличительные особенности
Подобрать квартиру в Челябинске с первого раза могут только люди, не предъявляющие особых...
Стоимость дизайн-проекта интерьера в Краснодарской студии
Стоимость дизайн-проекта интерьера в Краснодарской студии
Дизайн-проект реализует определенные задачи. Он формирует комфортное помещение для жизни,...
Тепловые пункты: преимущества установок и где заказать их изготовление
Тепловые пункты: преимущества установок и где заказать их изготовление
Тепловой пункт представляет собой комплекс устройств, предназначенных для поставки тепловой энергии...
Все новости