Кнут-Морис и Прат въвеждат алгоритъм за линейно време за проблема със съпоставянето на низове. Време за съпоставяне на 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“ по-долу:

проверете за null в java

Решение:

 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 смени.