TechCodeview

Кнутх-Моррис и Пратт уводе линеарни временски алгоритам за проблем подударања стрингова. Време упаривања од О (н) се постиже избегавањем поређења са елементом 'С' који је претходно био укључен у поређењу са неким елементом обрасца 'п' који треба да се упари. тј. враћање уназад на низу 'С' се никада не дешава

Компоненте КМП алгоритма:

1. Функција префикса (Π): Функција префикса, Π за образац обухвата знање о томе како се образац подудара са померањем самог себе. Ове информације се могу користити да се избегне бескорисно померање обрасца 'п'. Другим речима, ово омогућава избегавање враћања низа 'С'.

2. Утакмице КМП-а: Са низом 'С', узорком 'п' и префиксном функцијом 'Π' као улазима, пронађите појаву 'п' у 'С' и враћате број померања 'п' након којих се проналазе појаве.

Функција префикса (Π)

Следећи псеудо код израчунајте функцију префикса, Π:

 <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; 

Анализа времена трајања:

У горњем псеудо коду за израчунавање функције префикса, фор петља од корака 4 до корака 10 се покреће 'м' пута. Корак 1 до корак 3 захтева константно време. Отуда је време рада рачунске функције префикса О (м).

Пример: Израчунајте Π за образац 'п' испод:

јава формат стринга дугачак

Решење:

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

Након итерације 6 пута, израчунавање функције префикса је завршено:

КМП се подудара:

КМП Матцхер са узорком 'п', низом 'С' и функцијом префикса 'Π' као улазом, проналази подударање п у ​​С. Следећи псеудо код израчунајте одговарајућу компоненту КМП алгоритма:

 <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 

Анализа времена трајања:

Петља фор која почиње у кораку 5 изводи се 'н' пута, тј. све док је дужина низа 'С'. Пошто од корака 1 до корака 4 узимају константна времена, у времену рада доминира ово за петљу. Тако је време рада функције подударања О (н).

Пример: Дат је низ 'Т' и образац 'П' на следећи начин:

Хајде да извршимо КМП алгоритам да пронађемо да ли се 'П' појављује у 'Т'.

За 'п' функцију префикса, ? је претходно израчунато и гласи:

Решење:

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

Утврђено је да се образац 'П' сложеност јавља у низу 'Т'. Укупан број смена који се десио да би се пронашао меч је и-м = 13 - 7 = 6 смена.