Knuth-Morris i Pratt introdueixen un algorisme de temps lineal per al problema de concordança de cadenes. S'aconsegueix un temps de concordança de O (n) evitant la comparació amb un element de 'S' que s'ha implicat prèviament en comparació amb algun element del patró 'p' que s'ha de fer coincidir. és a dir, el retrocés a la cadena 'S' no es produeix mai
Components de l'algoritme KMP:
1. La funció de prefix (Π): La funció de prefix, Π per a un patró, encapsula el coneixement sobre com el patró coincideix amb el canvi de si mateix. Aquesta informació es pot utilitzar per evitar un canvi inútil del patró 'p.' En altres paraules, això permet evitar el retrocés de la cadena 'S'.
2. Les coincidències KMP: Amb la cadena 'S', el patró 'p' i la funció de prefix 'Π' com a entrades, trobeu l'ocurrència de 'p' a 'S' i retorna el nombre de torns de 'p' després dels quals es troben les ocurrències.
La funció de prefix (Π)
El pseudocodi següent calcula la funció 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 Π
Anàlisi del temps de funcionament:
Al pseudocodi anterior per calcular la funció de prefix, el bucle for del pas 4 al pas 10 s'executa 'm' vegades. El pas 1 al pas 3 pren un temps constant. Per tant, el temps d'execució de la funció de prefix de càlcul és O (m).
Exemple: Calculeu Π per al patró 'p' següent:
exemples d'autòmats dfa
Solució:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
Després d'iterar 6 vegades, el càlcul de la funció de prefix s'ha completat:
El KMP coincideix amb:
El KMP Matcher amb el patró 'p', la cadena 'S' i la funció de prefix 'Π' com a entrada, troba una coincidència de p a S. Seguint el pseudocodi calcula el component coincident de l'algorisme 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
Anàlisi del temps de funcionament:
El bucle for que comença al pas 5 s'executa 'n' vegades, és a dir, sempre que la longitud de la cadena 'S'. Com que el pas 1 al pas 4 pren temps constants, el temps d'execució està dominat per aquest per al bucle. Així, el temps d'execució de la funció de concordança és O (n).
Exemple: Donada una cadena 'T' i un patró 'P' de la següent manera:
Executem l'algoritme KMP per trobar si 'P' apareix a 'T'.
Per a 'p' la funció de prefix, ? s'ha calculat anteriorment i és el següent:
Solució:
Initially: n = size of T = 15 m = size of P = 7
S'ha trobat que el patró 'P' té complexitat en una cadena 'T'. El nombre total de torns que s'han fet per trobar la coincidència és i-m = 13 - 7 = 6 torns.