2015-04-12
1495
Рассмотрим сначала более простой случай. Пусть все символы строки-образца 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;
while j < M do begin
while (k > 0) and (S[j] <> 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 <= M) and (i <= N) do begin
while (j > 0) and (A[i] <> S[j]) do
j:= d[j];
i:= i + 1;
j:= j + 1;
end;
if j > M then
KMPSearch:= i – j + 1 {Успех}
else
KMPSearch:= 0; {Неудача}
end; {KMPSearch}
Можно доказать, что время работы алгоритма КМП Tмакс(n, m) = O(n+m). Это значительно лучше, чем оценка O(n×m) для прямого поиска, особенно для длинных строк-образцов.
