найбільш оптимальними (хоча б тому, що іноді виконують явно марну роботу, про що було сказано вище), тому ми перейдемо до наступного класу алгоритмів. Ці алгоритми з'явилися в результаті ретельного дослідження алгоритму послідовного пошуку. Дослідники хотіли знайти способи більш повно використовувати інформацію, отриману під час сканування (алгоритм прямого пошуку її просто викидає). Розглянемо алгоритм Кнута - Морріса - Пратта. h2> 1.3. Алгоритм Кнута - Морріса - Пратта (КМП).
Спочатку розглянемо деякі допоміжні затвердження. Для довільного слова X розглянемо всі його початку, що одночасно є його кінцями, і виберемо з них найдовше (не рахуючи, звичайно, самого слова X). Позначимо його n (X). Така функція зветься префікс - функции [13]. br/>
Приклади .
n (aba) = a, n (n (aba)) = n (a) = L;
n (abab) = ab, n (n (abab)) = n (ab) = L;
n (ababa) = aba, n (n (ababa)) = n (aba) = a, n (n (n (ababa))) = n (a) = L; n (abc) = L. p> Доведемо кілька використовуваних згодом фактів, а саме пропозицію (по [Шень, 1995, с.165-166]):
(1) Послідовність слів n (X), n (n (X)), n (n (n (X))), ... "Обривається" (на порожньому слові L).
(2) Всі слова n (X), n (n (X)), n (n (n (X))), ..., L є началами слова X.
(3) Будь-яке слово, одночасно є початком і кінцем слова X (крім самого X), входить до послідовність n (X), n (n (X)), ...., L.
Доказ .
(1) Тривіально, т.к. кожне слово коротше попереднього.
(2) Кожне з них (За визначенням) є початком попереднього. З тієї ж причини всі вони є кінцями слова X.
(3) Нехай слово Y є одночасно початком і кінцем X. Слово n (X) - найдовше з таких слів, так що Y не довше n (X). Обидва ці слова є началами X, тому більш короткий з них є початком більш довгого: Y є початок n (X). Аналогічно, Y є кінець n (X). Міркуючи по індукції, можна припускати, що твердження задачі правильно для всіх слів коротше X, зокрема, для слова n (X). Отже слово Y, що є кінцем і початком n (X), або одно n (X), або входить в послідовність n (n (X)), n (n (n (X))), ...,, L.
Пропозиція доведено.
Метод КМП використовує предобработку шуканої рядка, а саме: на її основі створюється префікс-функція. При цьому використовується наступна ідея: якщо префікс (він же суфікс) рядки довгою i довше одного символа, те він одночасно і префікс підрядка довгою i-1 (Лістинг 3). Таким чином, ми перевіряємо префікс попередньої підрядка, якщо ж той не підходить, то префікс її префікса, і т.д. Діючи тому, знаходимо найбільший шуканий префікс. Наступне питання, на який варто
Procedure PrefFunc (P: String; Var Fl: TMas);
Var n, i, j: Integer;
Begin
n: = Length (P);
Fl [1]: = 0;
For i: = 2 To n Do
Begin
j: = Fl [i-1];
While (j <> 0) And (P [j] <> P [i-1]) Do j: = Fl [j];
Fl [i]: = j +1;
End;
End;
відповісти: чому час роботи процедури лінійно, адже в ній присутній вкладений цикл? Ну, по-перше, привласнення префікс-функції відбувається чітко m раз, решту часу змінюється мінлива k. Так як в циклі while вона зменшується (P [k]
Лістинг 3
А зараз ми переходимо до самого алгоритму, що шукає підрядок в рядку (Лістинг 4).
Лістинг 4
Function KMPSearch (S, P: String): Integer;
{алгоpитмами Кнута-Моp
Іса-Пpатта, що встановлює}
{входження непорожній стор оки P в стpоку S }
Var Fl: TMas;
i, j, n, m: Integer;
Begin
n: = Length (S);
m: = Length (P);
PrefFunc (P, Fl);
j: = +1;
For i: = 1 To n Do
begin
While (j <> 0) And (P [j] <> S ​​[i]) do j: = Fl [j];
If j = m Then Break;
j: = j +1
end;
If (j = m) then Result: = i-j +1 Else Result: = 0;
End;
В В В В В В
Довести що ця програма працює за лінійний час, мо...
