X-PDF

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

Поделиться статьей

Рассмотрим сначала более простой случай. Пусть все символы строки-образца S различны. Начнем сравнивать символы S слева направо с первыми m символами строки A. Допустим, что несравнение символов произошло в позиции k £ m, т.е. первые k–1 букв A и S совпали. С какой позиции A следует начать новое сравнение с S? Поскольку символ ak–1 = sk–1, то ak–1 не может совпасть с предыдущими символами S (потому что все символы S различны). Значит, перед продолжением сравнения строк можно сдвинуть S так, чтобы ее первый символ сравнивался сразу с k-м символом A (т.е. с той позицией A, где было обнаружено несовпадение).

Если в S есть совпадающие символы, рассчитать величину сдвига несколько сложнее.

Определим dj как длину наибольшей подстроки из S, которая заканчивается в позиции j и совпадает с началом строки S во всех позициях, кроме последней. Это можно подробно расписать таким образом:

s[j – dj + 1] = s[1],

s[j – d j + 2] = s[2],

…, (7.1)

s[j – 1] = s[dj – 1],

но при этом s[j] ¹ s[dj]).

Если такой подстроки не существует, то положим dj = 0. Тогда нетрудно показать, что, если первое несовпадение при сравнении символов из A и S произошло на паре символов ai ¹ sj, то перед продолжением сравнения следует заменить индекс j на dj, а значение индекса i не изменять (т.е. надо сдвинуть строку S на j – dj позиций вдоль строки A). Действительно, поскольку символы a[i – dj + 1], a[i – d j + 2], …,
a[i – 1] успешно сравнились с символами s[j – dj + 1], s[j – d j + 2], …, s[j – 1], то они, согласно (7.1), должны сравниться и с символами s[1], s[2], …, s[dj – 1], а потому сравнение можно продолжать с пары символов a[i] и s[dj].

Если же значение j стало равно 0, то надо увеличить i и j на единицу, т.е. начать сопоставление символов заново с позиции i + 1 в строке A и с первой позиции в строке S.

Ниже приведены примеры значений dj, рассчитанных для различных строк-образцов.

1) a a a a a a 2) q w e r t y u i
  0 0 0 0 0 0   0 1 1 1 1 1 1 1
3) a a b a a b c 4) a b c d a c e f a b d f
  0 0 2 0 0 2 4   0 1 1 1 0 2 1 1 0 1 3 1
5) a b b a b b a c 6) a b a b a b a c a b c
  0 1 1 0 1 1 0 5   0 1 0 1 0 1 0 6 0 1 3

Рассмотрим работу алгоритма на примере, показанном на рис. 7.1. В строке A = ‘aabaabaaabaabc’ ищется подстрока S = ‘aabaabc’ (см. выше, пример 3).

  1 2 3 4 5 6 7 8 9 10 11 12 13 14
A: a a b a a b a a a b a a b c
Шаг 1: a a b a a b c              
Шаг 2:       a a b a a b c        
Шаг 3:               a a b a a b c

Рис. 7.1. Пример работы алгоритма Кнута, Морриса и Пратта

На первом шаге обнаруживается несовпадение букв ai и sj при i = 7 и j = 7. Выполняется присваивание j:= 4. Сравнение продолжается, пока при i = 9 и j = 6 не происходит очередное несовпадение. Делается присваивание j:= 2. На сей раз сравнение проходит успешно.

Отдельный вопрос – как лучше всего рассчитывать величины dj. В алгоритме на этот вопрос дается довольно неожиданный ответ. Задачу расчета dj для всех значений j можно рассматривать как модифицированную задачу поиска, в которой роль строки поиска играет S, а роль строки-образца – начальная часть той же строки. Поэтому вычисление dj выполняется примерно по тому же алгоритму, что и сам поиск вхождения S в A.

Ниже приведен текст функции, реализующей алгоритм поиска КМП.

function KMPSearch(A: StringN . S: StringM): Integer .

var

i, j, k: Integer .

d: Array[1..M] of Integer .

begin

{Вычисление d[j]}

j:= 1 .

k:= 0 .

d[1]:= 0 .

Представленная информация была полезной?
ДА
58.89%
НЕТ
41.11%
Проголосовало: 776

while j &lt . M do begin

while (k &gt . 0) and (S[j] &lt .&gt . S[k]) do

k:= d[k] .

j:= j + 1 .

k:= k + 1 .

if S[j] = S[k] then d[j]:= d[k]

else d[j]:= k .

end .

{Поиск}

i:= 1 .

j:= 1 .

while (j &lt .= M) and (i &lt .= N) do begin

while (j &gt . 0) and (A[i] &lt .&gt . S[j]) do

j:= d[j] .

i:= i + 1 .

j:= j + 1 .

end .

if j &gt . M then

KMPSearch:= i – j + 1 {Успех}

else

KMPSearch:= 0 . {Неудача}

end . {KMPSearch}

Можно доказать, что время работы алгоритма КМП Tмакс(n, m) = O(n+m). Это значительно лучше, чем оценка O(n×m) для прямого поиска, особенно для длинных строк-образцов.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.89%
НЕТ
41.11%
Проголосовало: 776

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет