Knuth-Morris et Pratt introduisent un algorithme de temps linéaire pour le problème de correspondance de chaînes. Un temps de correspondance de O (n) est obtenu en évitant la comparaison avec un élément de « S » qui a déjà été impliqué en comparaison avec un élément du motif « p » à mettre en correspondance. c'est-à-dire que le retour en arrière sur la chaîne « S » ne se produit jamais
Composants de l'algorithme KMP :
1. La fonction préfixe (Π) : La fonction préfixe, Π pour un modèle, encapsule les connaissances sur la manière dont le modèle correspond à son décalage. Cette information peut être utilisée pour éviter un décalage inutile du motif « p ». En d'autres termes, cela permet d'éviter un retour en arrière de la chaîne 'S'.
2. Les correspondances KMP : Avec la chaîne « S », le modèle « p » et la fonction de préfixe « Π » comme entrées, recherchez l'occurrence de « p » dans « S » et renvoie le nombre de décalages de « p » après lequel les occurrences sont trouvées.
La fonction préfixe (Π)
Le pseudo-code suivant calcule la fonction préfixe, Π :
<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 Π
Analyse du temps d'exécution :
Dans le pseudo-code ci-dessus pour calculer la fonction de préfixe, la boucle for de l'étape 4 à l'étape 10 s'exécute « m » fois. Les étapes 1 à 3 prennent un temps constant. Par conséquent, le temps d’exécution de la fonction de préfixe informatique est O (m).
Exemple: Calculez Π pour le modèle « p » ci-dessous :
strep c
Solution:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
Après 6 itérations, le calcul de la fonction préfixe est terminé :
Le KMP correspond :
Le KMP Matcher avec le modèle « p », la chaîne « S » et la fonction de préfixe « Π » en entrée, trouve une correspondance de p dans S. Le pseudo-code suivant calcule le composant de correspondance de l'algorithme 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
Analyse du temps d'exécution :
La boucle for commençant à l'étape 5 s'exécute « n » fois, c'est-à-dire aussi longtemps que la longueur de la chaîne « S ». Étant donné que les étapes 1 à 4 prennent des temps constants, le temps d'exécution en est dominé pour la boucle. Ainsi, le temps d'exécution de la fonction de correspondance est O (n).
Exemple: Étant donné une chaîne « T » et un motif « P » comme suit :
Exécutons l'algorithme KMP pour déterminer si « P » apparaît dans « T ».
Pour « p », la fonction de préfixe ? a été calculé précédemment et est le suivant :
Solution:
Initially: n = size of T = 15 m = size of P = 7
Il a été constaté que le modèle « P » présente une complexité dans une chaîne « T ». Le nombre total d'équipes qui ont eu lieu pour que la correspondance soit trouvée est i-m = 13 - 7 = 6 équipes.