backend / algorithmes-structures-donnees
Recherche de motifs : Knuth-Morris-Pratt (KMP)
Explication
Ce que vous allez apprendre
- Identifier pourquoi la recherche naïve de motif peut dégénérer en O(n×m) sur des textes répétitifs
- Expliquer l'idée centrale de KMP : ne jamais reculer dans le texte, seulement dans le motif
- Comprendre le rôle de la table d'échec (LPS), qui encode l'auto-similarité du motif
- Justifier pourquoi KMP garantit une complexité linéaire O(n + m), texte et motif confondus
- Reconnaître dans quels contextes réels une recherche de motif rapide est critique (éditeurs de texte, moteurs de recherche, bio-informatique)
Dans quel contexte ?
Un éditeur de texte doit implémenter la fonction "rechercher tout" pour trouver toutes les occurrences d'un motif dans un document de plusieurs millions de caractères, en temps réel pendant que l'utilisateur tape. Une recherche naïve, en O(n×m), deviendrait perceptiblement lente sur un motif répétitif dans un long document. KMP, en garantissant O(n + m) grâce à sa table d'échec précalculée, permet à la recherche de rester instantanée même sur les plus gros documents, sans jamais revenir en arrière dans le texte déjà lu.
D'abord, l'approche la plus naïve
Chercher toutes les occurrences d'un mot dans un texte semble trivial : comparer le motif à chaque position possible du texte, une par une.
Pourquoi cette approche naïve peut devenir très lente
Sur un texte très répétitif comme "aaaa...a", chaque échec de comparaison force à reculer et à recommencer presque depuis le début du motif, un gâchis de tout le travail déjà effectué.
| Approche | Complexité | Idée clé |
|---|---|---|
| Recherche naïve | O(n × m) au pire cas | Compare le motif à chaque position, sans mémoire des échecs précédents |
| KMP | O(n + m) garanti | Table d'échec (LPS) qui encode l'auto-similarité du motif |
Piège fréquent
La recherche naïve n'est pas "toujours" en O(n×m) en pratique : sur du texte aléatoire, elle reste souvent proche de O(n). C'est uniquement sur des motifs très répétitifs (comme "aaaa...ab" cherché dans "aaaa...a") que son pire cas se manifeste réellement — un piège classique si l'on ne teste que des cas "normaux".
L'observation qui change tout
Quand une comparaison échoue après avoir déjà matché plusieurs caractères, on sait déjà quelque chose sur ces caractères précis : pas besoin de les recomparer depuis le texte.
Comment KMP exploite cette observation
L'algorithme précalcule une "table d'échec" (ou table LPS) qui indique, pour chaque position du motif, jusqu'où on peut se replier DANS LE MOTIF, sans jamais reculer dans le texte.
Pourquoi cette table est le cœur de l'algorithme
Elle encode l'auto-similarité du motif : si le motif contient lui-même des répétitions internes, cette information permet de "sauter" directement à la bonne position après un échec, au lieu de tout recommencer.
Astuce
La table LPS (Longest Prefix Suffix) répond, pour chaque position i du motif, à la question : « quel est le plus long préfixe du motif qui est aussi un suffixe de motif[0..i] ? » C'est cette information, calculée une seule fois en O(m), qui évite tout retour en arrière dans le texte.
Le résultat de cette précomputation
Cela transforme une complexité potentiellement quadratique O(n×m) en une complexité garantie linéaire O(n+m), quel que soit le texte, même le plus répétitif.
Pourquoi ça compte en pratique
Cette technique est utilisée dans des outils réels comme grep, les éditeurs de texte, ou la comparaison de séquences biologiques (ADN, protéines), où les motifs répétitifs sont fréquents.
Vers la suite
KMP résout ce problème en évitant intelligemment de reculer dans le texte. La prochaine leçon attaque le même problème sous un angle complètement différent, en comparant des empreintes numériques plutôt que des caractères : Rabin-Karp.
Commandes & code
Recherche de motifs : KMP
KMP trouve toutes les occurrences d'un motif dans un texte en O(n + m), sans jamais reculer dans le texte.
def construire_table_echec(motif: str) -> list[int]:
# lps[i] = longueur du plus long préfixe de motif[:i+1] qui est aussi un suffixe propre
lps = [0] * len(motif)
longueur = 0 # longueur du préfixe=suffixe courant
i = 1
while i < len(motif):
if motif[i] == motif[longueur]:
longueur += 1
lps[i] = longueur
i += 1
elif longueur > 0:
longueur = lps[longueur - 1] # recule dans la table, jamais dans le texte
else:
lps[i] = 0
i += 1
return lps
def kmp_recherche(texte: str, motif: str) -> list[int]:
# Trouve TOUTES les occurrences de motif dans texte en O(n + m)
if not motif:
return []
lps = construire_table_echec(motif)
occurrences = []
i = j = 0 # i : index dans texte, j : index dans motif
while i < len(texte):
if texte[i] == motif[j]:
i += 1
j += 1
if j == len(motif):
occurrences.append(i - j) # occurrence trouvée
j = lps[j - 1] # continue pour trouver les occurrences suivantes
elif j > 0:
j = lps[j - 1] # ne revient jamais en arrière sur i
else:
i += 1
return occurrences
texte = "ababcabababcabcabab"
motif = "abcab"
assert kmp_recherche(texte, motif) == [2, 10]
assert construire_table_echec("aabaaab") == [0, 1, 0, 1, 2, 2, 3]
assert kmp_recherche("aaaaaaa", "aaa") == [0, 1, 2, 3, 4] # occurrences chevauchantes trouvées
assert kmp_recherche("bonjour", "xyz") == []
# Complexité : O(n + m) contre O(n*m) en force brute -- déterminant sur des textes/motifs répétitifs
# (ex: "aaaa...a" où la force brute recule constamment dans le texte)Résumé
- La table d'échec (
lps) précalcule, pour chaque position du motif, le plus long préfixe qui est aussi suffixe : elle évite tout retour en arrière dans le texte. - Complexité garantie O(n + m), y compris sur les pires cas pour la recherche naïve (motifs très répétitifs).
- Utilisé en pratique dans
grep, l'édition de texte, et la détection de motifs biologiques (ADN, protéines).
Exercices pratiques
Mission : accélérer le moteur de recherche qui rame sur les textes répétitifs
Objectif : Tracer manuellement la table d'échec KMP et diagnostiquer le pire cas de la recherche naïve.
Contexte
L'équipe d'un éditeur de texte reçoit une plainte : la fonction "rechercher tout" devient perceptiblement lente uniquement sur certains documents très répétitifs (par exemple une longue suite de la lettre "a" suivie d'un motif proche mais pas identique), alors qu'elle est instantanée sur des textes normaux. Le code actuel utilise une recherche naïve caractère par caractère.