Knuth-Morris e Pratt introducono un algoritmo temporale lineare per il problema della corrispondenza delle stringhe. Un tempo di abbinamento di O (n) si ottiene evitando il confronto con un elemento di 'S' che è stato precedentemente coinvolto rispetto a qualche elemento del modello 'p' da abbinare. cioè, il backtracking sulla stringa 'S' non avviene mai
Componenti dell'algoritmo KMP:
1. La funzione prefisso (Π): La funzione prefisso, Π per un modello, incapsula la conoscenza su come il modello corrisponde allo spostamento di se stesso. Questa informazione può essere utilizzata per evitare uno spostamento inutile del modello 'p.' In altre parole, ciò consente di evitare il backtracking della stringa 'S.'
2. Le partite KMP: Con la stringa 'S', il modello 'p' e la funzione prefisso 'Π' come input, trova l'occorrenza di 'p' in 'S' e restituisce il numero di spostamenti di 'p' dopo i quali vengono trovate le occorrenze.
La funzione prefisso (Π)
Il seguente pseudo codice calcola la funzione del prefisso, Π:
<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 Π
Analisi del tempo di esecuzione:
Nello pseudocodice precedente per il calcolo della funzione del prefisso, il ciclo for dal passaggio 4 al passaggio 10 viene eseguito 'm' volte. I passaggi da Step1 a Step3 richiedono un tempo costante. Quindi il tempo di esecuzione della funzione di calcolo del prefisso è O (m).
Esempio: Calcola Π per il modello 'p' di seguito:
stringa Java di concatenazione
Soluzione:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
Dopo 6 iterazioni, il calcolo della funzione prefisso è completo:
Il KMP corrisponde:
Il KMP Matcher con il modello 'p', la stringa 'S' e la funzione prefisso 'Π' come input, trova una corrispondenza di p in S. Il seguente pseudo codice calcola il componente corrispondente dell'algoritmo 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
Analisi del tempo di esecuzione:
Il ciclo for che inizia nel passaggio 5 viene eseguito 'n' volte, ovvero finché la lunghezza della stringa 'S.' Poiché i passaggi da 1 a 4 richiedono tempi costanti, il tempo di esecuzione è dominato da questo per il ciclo. Pertanto il tempo di esecuzione della funzione di corrispondenza è O (n).
Esempio: Data una stringa 'T' e un modello 'P' come segue:
Eseguiamo l'algoritmo KMP per scoprire se 'P' ricorre in 'T.'
Per 'p' la funzione del prefisso, ? è stato calcolato in precedenza ed è il seguente:
Soluzione:
Initially: n = size of T = 15 m = size of P = 7
È stato riscontrato che il modello 'P' è complesso in una stringa 'T'. Il numero totale di turni necessari per trovare la corrispondenza è i-m = 13 - 7 = 6 turni.