L'algorithme de Knuth, Morris et Pratt est une variante de l'algorithme de Morris et Pratt qui est lui même une amélioration de l'algorithme naïf.
L'algorithme naïf est le plus simple. Il procède de la manière suivante. Pour chaque position possible du motif dans le texte, on teste si cette position est une occurrence du motif. Ce test est effectué en comparant les caractères du motif avec les caractères du texte de gauche à droite. Si tous les caractères du motif sont égaux aux caractères du texte aux positions correspondantes, une occurrence a été trouvée et la position de cette occurrence est retournée. Sinon, la recherche se poursuit en passant à la position suivante.
Lorsqu'un échec a lieu dans l'algorithme naïf, c'est-à-dire lorsqu'un un caractère du motif est différent du caractère correspondant dans le texte, la recherche reprend à la position suivante en repartant au début du motif. Si le caractère qui a provoqué l'échec n'est pas au début du motif, cette recherche commence par comparer une partie du motif avec une partie du texte qui a déjà été comparée avec le motif. L'idée de départ de l'algorithme de Morris et Pratt est d'éviter ces comparaisons inutiles.
On commence par quelques définitions. Un préfixe d'un mot w est un mot u qui est un début de w. Un suffixe d'un mot w est un mot u qui est une fin de w. Un préfixe ou un suffixe d'un mot w est dit propre s'il n'est pas égal à w. Un bord d'un mot w est un mot u différent de w qui est à la fois préfixe et suffixe de w. Pour un mot w, on note bord(w) le plus long bord de w. On remarque qu'un bord de w est soit bord(w) lui-même soit un bord de bord(w). On en déduit que l'ensemble des bords de w est égal à {bord(w), bord(bord(w)), ..., bordk(w)} où k est le plus petit entier tel que bordk(w) est le mot vide.
Soit w un mot et a une lettre. Un bord du mot wa est de la forme ua où u est un bord de w. Réciproquement un mot de la forme ua où u est un bord de w est toujours un suffixe de wa mais pas nécessairement. Le plus long bord de wa est donc égal à ua où u est le plus long bord de w telle que la lettre suivante de w après le préfixe u est égale à a.
Soit w le préfixe de longueur i du motif, c'est-à-dire le mot p0...pi-1. On note s[i] la longueur du plus long bord de w. On remarque que les longueurs des bords de w est égale à la suite {s[i], s[s[i]], ..., sk[i]}. La valeur de s[i+1] est donc à égale à 1 + sk[i] ou k est le plus petit entier tel que que la lettre à la position sk[i] est égale à pi.
Cet algorithme est une amélioration de l'algorithme précédent. L'idée sous-jacente est de pas considérer les bords qui sont suivis de la même lettre que celle qui a provoqué l'échec. Soit w le préfixe de longueur i du motif, c'est-à-dire le mot p0...pi-1. Un bord compatible de w est un bord de w qui est suivi dans w d'une lettre différente de w. On note r[i] la longueur du plus long bord compatible de w.
Pour calculer la fonction r, on utilise les deux relations suivantes entre les fonctions r et s. La première relation permet de calculer r à partir de s. Pour tout i on a, r[i] est égal à
La seconde relation permet de calculer s à partir de r. La longueur s[i+1] est égal 1 + rk[s[i]] où k est le plus petit entier tel que la lettre à la position rk[s[i]] est égale à pi. Soit w le préfixe de longueur i du motif et soit a la lettre pi et soit u le plus long bord de w. La longueur de u est s[i]. Si la lettre à la position s[i] est égale à la lettre a alors s[i+1] est justement égal à 1+s[i]. Sinon, le plus long bord de wa est un bord de u et comme la lettre qui suit u est différente de la lettre a, alors le plus long bord de wa est de la forme va où v est un bord compatible de u.
La classe Pattern contient une implémentation des différents algorithmes de recherche de motif sous forme de méthode statiques. Voici les mêmes fonctions programmées en C.