Fonction préfixe KMP
Trouver un motif en O(n + m)
Fonction préfixe KMP est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème de recherche de motifs
Vous voulez trouver où un petit motif apparaît dans un grand texte. Les vérifications naïves sont lentes, alors les concours récompensent un parcours plus astucieux. 🔍
Pourquoi la recherche naïve est coûteuse
Comparer le motif à chaque position peut coûter O(n*m) en temps. Sur de grandes entrées, cela dépasse discrètement votre limite de temps.
Découvrez la fonction préfixe
La fonction préfixe mesure, à chaque position, la longueur du plus long préfixe strict qui est aussi un suffixe. C’est le cœur de KMP.
Préfixe et suffixe stricts
Un préfixe ou suffixe strict exclut la chaîne entière. Pour ababa, la plus longue paire correspondante a une longueur de 3 : aba.
Ce que contient pi[i]
Nous stockons les valeurs dans un tableau appelé pi. Ici, pi[i] est la longueur de ce plus long préfixe-suffixe pour la sous-chaîne se terminant à l’indice i.
Construire pi en une seule passe
Construisez pi de gauche à droite en réutilisant les valeurs précédentes au lieu de tout revérifier depuis le début. C’est précisément cette réutilisation qui fait fonctionner la méthode.
def prefix_function(s):
pi = [0] * len(s)
return piLa boucle de repli
Lorsque les caractères diffèrent, revenez à pi[k-1] au lieu de réinitialiser à zéro. Vous évitez ainsi de refaire le travail.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Prolonger une correspondance
Si les caractères actuels correspondent, augmentez la longueur de un et enregistrez-la. En cas de différence à zéro, la valeur reste simplement nulle.
if s[i] == s[k]:
k += 1
pi[i] = kRechercher avec l’astuce
Pour rechercher un motif dans un texte, assemblez-les ainsi : motif + séparateur + texte. Toute valeur de pi égale à la longueur du motif signale une correspondance complète.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Pourquoi un séparateur est nécessaire
Le séparateur est un symbole qui n’appartient à aucune des deux chaînes. Il empêche les correspondances de traverser la jonction et de produire de fausses détections.
Le gain du temps linéaire
La construction et la recherche s’exécutent toutes deux en O(n + m). Chaque caractère est traité une fois, ce qui permet à KMP de gérer de très grandes entrées de concours.
Vérification rapide
Vérifiez votre compréhension de ce que mémorise la fonction préfixe.
Récapitulatif : KMP en bref
Vous avez appris la fonction préfixe : construisez pi une fois, utilisez le repli en cas de différence et effectuez la recherche en temps linéaire. Voilà KMP en bref. 🎯
Questions Fréquemment Posées
La leçon « Fonction préfixe KMP » est-elle gratuite ?
Oui — le texte complet de « Fonction préfixe KMP » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fonction préfixe KMP » ?
Trouver un motif en O(n + m) Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Fonction préfixe KMP » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Fonction préfixe KMP
- Hachage polynomial de chaînes
- Fonction Z pour rechercher un motif
- Tries pour les recherches par préfixe