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

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 &#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 

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.