TechCodeview

Knuts-Morris un Pratt ievieš lineāro laika algoritmu virkņu atbilstības problēmai. O (n) atbilstības laiks tiek panākts, izvairoties no salīdzināšanas ar elementu “S”, kas iepriekš ir bijis iesaistīts, salīdzinot ar kādu saskaņojamo modeļa “p” elementu. i., atkāpšanās no virknes 'S' nekad nenotiek

KMP algoritma sastāvdaļas:

1. Prefiksa funkcija (Π): Prefiksa funkcija Π paraugam ietver zināšanas par to, kā modelis sakrīt ar paša maiņu. Šo informāciju var izmantot, lai izvairītos no bezjēdzīgas raksta 'p' maiņas. Citiem vārdiem sakot, tas ļauj izvairīties no virknes 'S.'

2. KMP spēles: Izmantojot virkni 'S', paraugu 'p' un prefiksa funkciju 'Π' kā ievadi, atrodiet 'p' sastopamību 'S' un atgriež 'p' maiņu skaitu, pēc kurām tiek atrasti gadījumi.

Prefiksa funkcija (Π)

Pēc pseidokoda aprēķina prefiksa funkciju, Π:

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

Darbības laika analīze:

Iepriekš minētajā pseidokodā prefiksa funkcijas aprēķināšanai cilpa for no 4. darbības līdz 10. darbībai tiek izpildīta “m” reizes. No 1. līdz 3. darbībai nepieciešams pastāvīgs laiks. Tādējādi prefiksa funkcijas skaitļošanas laiks ir O (m).

Piemērs: Aprēķiniet Π paraugam “p” zemāk:

atšķirība starp gigabaitu un megabaitu

Risinājums:

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

Pēc 6 reizes atkārtošanas prefiksa funkcijas aprēķināšana ir pabeigta:

KMP spēles:

KMP atbilstības meklētājs ar šablonu “p”, virkni “S” un prefiksa funkciju “Π” kā ievadi, atrod p atbilstību S. Pēc pseidokoda aprēķina atbilstošo KMP algoritma komponentu:

 <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 

Darbības laika analīze:

For cilpa, kas sākas 5. darbībā, tiek izpildīta 'n' reizes, t.i., tik ilgi, kamēr virknes garums ir 'S'. Tā kā no 1. līdz 4. darbībai ir nepieciešams konstants laiks, cilpas darbības laikā dominē šis. Tādējādi atbilstības funkcijas darbības laiks ir O (n).

Piemērs: Dota virkne “T” un raksts “P” šādi:

Izpildīsim KMP algoritmu, lai noskaidrotu, vai “P” ir “T”.

'p' prefiksa funkcijai ? tika aprēķināts iepriekš un ir šāds:

Risinājums:

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

Ir konstatēts, ka virknē “T” modelis “P” ir sarežģīts. Kopējais maiņu skaits, kas notika, lai atrastu spēli, ir i-m = 13 - 7 = 6 maiņas.