Comprendre et implémenter l’algorithme de Knuth‑Morris‑Pratt pour la recherche de sous‑chaîne

Introduction

La recherche d’une sous‑chaîne dans un texte est un problème fondamental en informatique. La solution naïve, qui compare le motif à chaque position du texte, a une complexité O(n·m) (n = longueur du texte, m = longueur du motif). L’algorithme de Knuth‑Morris‑Pratt (KMP) élimine les comparaisons redondantes en pré‑calculant un tableau de bord (ou fonction de préfixe) qui décrit les recouvrements du motif. Le résultat : une recherche en temps linéaire O(n+m). Cet article décortique le principe du KMP, propose une implémentation Python claire et discute les optimisations possibles.

Le principe du KMP

1. Pré‑traitement du motif – on construit le tableau lps (Longest Proper Prefix which is also Suffix). Chaque entrée lps[i] indique la longueur du plus long préfixe du sous‑motif pat[0…i] qui est aussi suffixe de ce sous‑motif.
2. Recherche – lors de la comparaison texte/motif, lorsqu’un caractère ne correspond pas, on ne revient pas au début du motif. On utilise lps pour savoir jusqu’où on peut reprendre la comparaison sans perdre d’information déjà validée.

Le tableau lps garantit que chaque caractère du texte est examiné au plus une fois, d’où la complexité linéaire.

Exemple de construction du tableau lps

Motif : ABABCABAB

i	pat[i]	lps[i]
0	A	0
1	B	0
2	A	1
3	B	2
4	C	0
5	A	1
6	B	2
7	A	3
8	B	4

Ce tableau indique, par exemple, qu’après une mauvaise correspondance en position 4, le motif peut reprendre à l’indice 0 (car lps[3]=2).

Implémentation en Python

Voici une implémentation concise du KMP, respectant les conventions Python et facilement réutilisable dans des projets de certification.

def compute_lps(pattern: str) -> list[int]:
    """Calcule le tableau LPS du motif.
    
    Args:
        pattern: le motif à pré‑traiter.
    Returns:
        Une liste d'entiers de même longueur que *pattern*.
    """
    lps = [0] * len(pattern)
    length = 0  # longueur du préfixe précédent
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
                # on ne progresse pas i ici, on ré‑évalue avec le nouveau length
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text: str, pattern: str) -> list[int]:
    """Recherche toutes les occurrences du *pattern* dans *text*.
    
    Retourne la liste des indices de début de chaque occurrence.
    """
    if not pattern:
        return []
    lps = compute_lps(pattern)
    i = j = 0  # i = indice texte, j = indice motif
    occurrences = []
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                occurrences.append(i - j)
                j = lps[j - 1]  # recherche d'éventuelles occurrences qui se chevauchent
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return occurrences

Points d’attention

• Le pré‑traitement est O(m). La recherche proprement dite est O(n).
• La fonction gère les motifs vides et les chevauchements (ex. motif AAA dans texte AAAAA).
• Le code utilise les annotations de type (list[int]) pour renforcer la lisibilité, ce qui est apprécié dans les examens de certification.

Optimisations et cas d’usage

• Gestion de l’alphabet : si l’alphabet est petit (ex. ADN, ACGT), on peut remplacer les comparaisons de caractères par des indexations dans un tableau d’entiers, ce qui accélère légèrement l’exécution.
• Recherche simultanée de plusieurs motifs : le prolongement naturel du KMP est l’algorithme Aho‑Corasick, qui construit un automate à partir de plusieurs motifs. Il conserve la même complexité linéaire globale.
• Applications concrètes
  • Analyse de logs : détection de patterns de sécurité dans de gros fichiers texte.
  • Compilateurs : recherche de séquences tokenisées dans le code source.
  • Bioinformatique : recherche de séquences d’ADN ou de protéines dans de grands génomes.

Conclusion

Le Knuth‑Morris‑Pratt illustre comment un pré‑traitement intelligent transforme un problème naïvement quadratique en un algorithme linéaire. Maîtriser le calcul du tableau lps et son utilisation pendant la recherche est indispensable pour toute certification portant sur les algorithmes de texte. L’implémentation Python ci‑dessus est à la fois lisible et performante, et sert de base solide pour des extensions (Aho‑Corasick, recherche hors‑ligne, etc.). En s’exerçant sur différents types de motifs et de textes, les développeurs renforcent leurs compétences en analyse de complexité et en optimisation de code, deux critères évalués fréquemment dans les certifications IT.