Introduction à la Recherche de Motifs

La recherche d'un motif dans une chaîne de caractères est une opération courante. Par exemple, chercher le motif cdb dans la chaîne cible abcbdbddd peut être réalisé de plusieurs manières. On note généralement :

• Chaîne cible T : la chaîne dans laquelle on cherche (exemple : abcbdbddd)
• Motif S : la sous-chaîne recherchée (exemple : cdb)
• Indice i : position courante dans la chaîne cible (commence à 1)
• Indice j : position courante dans le motif (commence à 1)

Algorithme Naïf (Force Brute)

L'algorithme naïf compare le motif à la chaîne cible en commençant par la première position. En cas d'échec, il décale le motif d'une position et recommence la comparaison depuis le début du motif.

Illustration avec T = abeabeabas et S = abeabas :

• Étape 1 : a correspond, on continue.
• Étape 2-3 : b et e correspondent.
• Étape 4 : a correspond.
• Étape 5 : b correspond.
• Étape 6 : e (cible) ≠ a (motif). Échec. On décale le motif d'une position dans la cible.
• Étape 7 : On recommence la comparaison depuis le début du motif avec la position 2 de la cible.

On observe que l'algorithme naïf est inefficace car, après un échec, il revient en arrière dans la chaîne cible et recommence depuis le début du motif, ignorant les informations déjà acquises lors de la comparaison précédente.

Propriété des Bordures (Border)

L'optimisation de KMP repose sur la notion de border. Pour une position i dans une chaîne, le border est la longueur du plus long préfixe de la sous-chaîne [1..i] qui est aussi un suffixe (sans considérer la chaîne entière).

Exemple : Pour la chaîne aba :

• Position 1 : chaîne a → border = 0
• Position 2 : chaîne ab → border = 0
• Position 3 : chaîne aba → border = 1 (car le préfixe a est égal au suffixe a)

Cette propriété est cruciale pour KMP. Lors d'une discordance à la position j du motif, on peut réutiliser les connaissances acquises : au lieu de recommmencer au début du motif (j=1), on peut placer j à la valeur border[j-1] + 1 (si j > 1). Cela évite de re-comparer des parties déjà vérifiées.

Calcul Efficace du Tableau des Bordures

Le calcul du tableau border (parfois appelé next ou π) peut être effectué en O(n). L'idée est de construire ce tableau itérativement.

Soit border[i] la longueur du plus long préfixe propre qui est aussi suffixe pour la sous-chaîne S[1..i].

• Initialisation : border[1] = 0.
• Pour i de 2 à la longueur de S, on compare S[border[i-1] + 1] avec S[i]. Si égalité, border[i] = border[i-1] + 1. Sinon, on réduit j en appliquant récursivement j = border[j] jusqu'à trouver une correspondance ou que j devienne 0.

char S[maxn];
int border[maxn];

void computeBorder(int len) {
    int j = 0;
    border[1] = 0;
    for (int i = 2; i <= len; i++) {
        while (j > 0 && S[i] != S[j + 1])
            j = border[j];
        if (S[i] == S[j + 1])
            j++;
        border[i] = j;
    }
}

Algorithme KMP

L'algorithme KMP combine la recherche avec le tableau des bordures précalculé. On parcourt la chaîne cible T avec l'indice i et on maintient un indice j pour le motif S. En cas de discordance, on utilise le tableau border pour ajuster j sans revenir en arrière dans T.

Procédure de recherche :

• Initialiser j = 0.
• Pour chaque position i dans T (de 1 à la longueur de T) :
  • Tant que j > 0 et T[i] != S[j+1], faire j = border[j].
  • Si T[i] == S[j+1], incrémenter j.
  • Si j atteint la longueur du motif, une occurence est trouvée à la position i - len(S) + 1. On peut alors réinitialiser j = border[j] pour continuer la recherche d'occurrences suivantes.

int j = 0;
int lenT = strlen(T + 1);
int lenS = strlen(S + 1);

for (int i = 1; i <= lenT; i++) {
    while (j > 0 && T[i] != S[j + 1])
        j = border[j];
    if (T[i] == S[j + 1])
        j++;
    if (j == lenS) {
        printf("Occurrence found at index: %d\n", i - lenS + 1);
        j = border[j];
    }
}

L'algorithme KMP offre une complexité linéaire O(n + m) où n est la longueur de la chaîne cible et m celle du motif, ce qui le rend beaucoup plus efficace que l'approche naïve pour de longues chaînes.