Compteur de pas de recherche KMP | Table d'échec et économie de pas en clair

Observez l'algorithme de Knuth-Morris-Pratt à l'œuvre sur votre propre texte. Cet outil construit la table de la fonction d'échec LPS de votre motif, exécute le parcours KMP en temps linéaire et compte le nombre de comparaisons de caractères de KMP face à une recherche naïve à double boucle sur la même entrée.

💡 À propos de cet outil

La plupart des explications de KMP s'arrêtent à « c'est en O(n+m), faites-moi confiance ». Il reste un manque : on peut réciter la borne de complexité sans ressentir d'où vient le gain, ni pourquoi la fonction d'échec compte. Et au moment d'implémenter KMP pour un TP ou un entretien, la table LPS est précisément ce qui fait trébucher.

Ce compteur comble ce manque avec des chiffres concrets issus de votre saisie. Entrez n'importe quel motif et texte, et vous voyez le tableau LPS ligne par ligne (i, p[i], lps[i]), les positions exactes de correspondance et le décompte des comparaisons en vis-à-vis. Comme les chiffres KMP et naïf proviennent du même texte, vous trouvez vous-même le point d'équilibre : sur un texte aléatoire l'écart est faible, mais avec un motif comme aaaab face à une longue suite de a, la recherche naïve explose tandis que KMP reste linéaire. Ce contraste est le cœur de l'algorithme, et vous pouvez le reproduire à volonté.

🧐 Questions fréquentes

Que stocke réellement la table LPS ? LPS[i] est la longueur du plus long préfixe propre de p[0..i] qui est aussi un suffixe de p[0..i]. En cas de discordance, KMP ramène le pointeur du motif à LPS[j-1] au lieu de repartir de zéro, ce qui supprime les comparaisons redondantes.

Comment une « comparaison » est-elle comptée ici ? Un pas équivaut à une comparaison entre un caractère du motif et un caractère du texte. Les replis de pointeur que KMP effectue via la table LPS ne sont pas comptés comme des pas, car ils ne touchent aucun caractère du texte. La recherche naïve compte chaque comparaison de la boucle interne.

Pourquoi l'accélération dépasse-t-elle parfois à peine 1x ? Sur un texte naturel ou aléatoire, les discordances surviennent souvent dès le premier caractère, donc la recherche naïve recule rarement loin. L'avantage de KMP apparaît avec des motifs à longs préfixes répétés face à un texte adverse, où la recherche naïve réexamine plusieurs fois les mêmes caractères.

Détecte-t-il les correspondances qui se chevauchent ? Oui. Après une correspondance complète, KMP réinitialise j à LPS[m-1], donc les occurrences chevauchantes (comme aa dans aaaa) sont toutes signalées. Les indices sont en base 0.

Les espaces et les symboles comptent-ils ? Oui. La recherche se fait au niveau caractère, donc espaces, sauts de ligne et ponctuation sont comparés tels quels. Aucune limite de longueur sur les deux champs, même si les motifs plus courts construisent leur table LPS plus vite.

📚 Le saviez-vous

KMP a été publié en 1977 par Donald Knuth, James Morris et Vaughan Pratt. La recherche par automate fini que KMP préfigure relie le traitement des chaînes à la théorie des langages : la fonction d'échec est en réalité un petit automate fini compilé à partir du motif. Cette même idée de fonction préfixe réapparaît loin de la recherche de chaînes : elle soutient des techniques de programmation compétitive comme compter les bordures distinctes d'une chaîne ou trouver la plus petite période d'une séquence répétée.