TechCodeview

Кнут-Морріс і Пратт представляють алгоритм лінійного часу для проблеми зіставлення рядків. Час узгодження O (n) досягається шляхом уникнення порівняння з елементом 'S', який раніше був залучений до порівняння з деяким елементом шаблону 'p', який потрібно зіставити. тобто повернення до рядка 'S' ніколи не відбувається

Компоненти алгоритму KMP:

1. Функція префікса (Π): Функція префікса, Π для шаблону, інкапсулює знання про те, як шаблон збігається зі зсувом самого себе. Цю інформацію можна використати, щоб уникнути марного зсуву шаблону «p». Іншими словами, це дає змогу уникнути повернення рядка 'S'.

2. Матчі KMP: Використовуючи рядок «S», шаблон «p» і функцію префікса «Π» як вхідні дані, знайдіть входження «p» у «S» і повертає кількість зсувів «p», після яких знайдено входження.

Функція префікса (Π)

Наступний псевдокод обчислює функцію префікса, Π:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

Аналіз тривалості роботи:

У наведеному вище псевдокоді для обчислення функції префікса цикл for від кроку 4 до кроку 10 виконується 'm' разів. Крок 1–3 займає постійний час. Отже, час роботи обчислювальної префіксної функції дорівнює O (m).

приклад: Обчисліть Π для шаблону 'p' нижче:

вік Ріанни

рішення:

 Initially: m = length [p] = 7 Π [1] = 0 k = 0 

Після 6 ітерацій обчислення функції префікса завершено:

KMP відповідає:

KMP Matcher із шаблоном «p», рядком «S» і функцією префікса «Π» як вхідні дані знаходить відповідність p у S. Наступний псевдокод обчислює компонент відповідності алгоритму KMP:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

Аналіз тривалості роботи:

Цикл for, що починається на кроці 5, виконується «n» разів, тобто стільки, скільки довжина рядка «S». Оскільки кроки з 1 по 4 займають постійний час, час виконання циклу домінує. Таким чином, час роботи функції узгодження дорівнює O (n).

приклад: Дано рядок «T» і шаблон «P» таким чином:

Давайте виконаємо алгоритм KMP, щоб визначити, чи зустрічається «P» у «T».

Для 'p' функція префікса, ? було обчислено раніше і виглядає наступним чином:

рішення:

 Initially: n = size of T = 15 m = size of P = 7 

Було виявлено, що складність шаблону 'P' виникає в рядку 'T'. Загальна кількість зсувів, які мали місце для пошуку збігу, становить i-m = 13 - 7 = 6 зрушень.