Knuth-Morris și Pratt introduc un algoritm de timp liniar pentru problema potrivirii șirurilor. Un timp de potrivire al lui O (n) se realizează prin evitarea comparării cu un element din „S” care a fost implicat anterior în comparație cu un element din modelul „p” care trebuie asortat. adică, înapoi pe șirul „S” nu apare niciodată
Componentele algoritmului KMP:
1. Funcția de prefix (Π): Funcția de prefix, Π pentru un model, încapsulează cunoștințele despre modul în care modelul se potrivește cu schimbarea în sine. Aceste informații pot fi folosite pentru a evita o schimbare inutilă a modelului „p.”. Cu alte cuvinte, acest lucru permite evitarea retrocedării șirului „S”.
2. Potrivirile KMP: Cu șirul „S”, modelul „p” și funcția de prefix „Π” ca intrări, găsiți apariția lui „p” în „S” și returnează numărul de schimburi ale lui „p” după care sunt găsite aparițiile.
Funcția de prefix (Π)
Următorul pseudo-cod calculează funcția de prefix, Π:
<strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
Analiza timpului de rulare:
În pseudocodul de mai sus pentru calcularea funcției de prefix, bucla for de la pasul 4 la pasul 10 rulează de „m” ori. Pasul 1 până la Pasul 3 durează constant. Prin urmare, timpul de funcționare al funcției de prefix de calcul este O (m).
Exemplu: Calculați Π pentru modelul „p” de mai jos:
șir de concatenare java
Soluţie:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
După repetarea de 6 ori, calculul funcției de prefix este complet:
KMP se potrivește cu:
KMP Matcher cu modelul „p”, șirul „S” și funcția de prefix „Π” ca intrare, găsește o potrivire a lui p în S. Urmând pseudocodul, calculează componenta de potrivire a algoritmului KMP:
<strong>KMP-MATCHER (T, P)</strong> 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [q] // look for the next match
Analiza timpului de rulare:
Bucla for care începe în pasul 5 rulează de „n” ori, adică atâta timp cât lungimea șirului „S”. Deoarece pasul 1 până la pasul 4 au timpi constante, timpul de rulare este dominat de acesta pentru buclă. Astfel, timpul de rulare al funcției de potrivire este O (n).
Exemplu: Dat un șir „T” și model „P” după cum urmează:
Să executăm algoritmul KMP pentru a afla dacă „P” apare în „T”.
Pentru „p” funcția de prefix, ? a fost calculat anterior și este după cum urmează:
Soluţie:
Initially: n = size of T = 15 m = size of P = 7
S-a constatat că modelul „P” are complexitate într-un șir „T”. Numărul total de schimburi care au avut loc pentru ca potrivirea să fie găsită este i-m = 13 - 7 = 6 schimburi.