La capacité d'une personne à aller loin ne se mesure pas à la vitesse à laquelle elle avance dans des circonstances favorables, mais à la rapidité avec laquelle elle retrouve son essence dans l'adversité.

— KMP

LeetCode 28 : Trouver l'index de la première occurrence d'une sous-chaîne

Lien du problème : LeetCode 28. Trouver l'index de la première occurrence d'une sous-chaîne

Description du problème : Étant donné deux chaînes, haystack et needle, trouvez la première occurrence de needle dans haystack et renvoyez son index. Si needle n'apparaît pas dans haystack, renvoyez -1. Essentiellement, il s'agit d'implémenter la fonction de bibliothèque strstr().

Approche : L'approche la plus simple est la force brute, utilisant deux boucles imbriquées. Cependant, sa complexité temporelle est O(n^2). Pour optimiser cela, nous pouvons utiliser l'algorithme KMP (Knuth-Morris-Pratt). KMP exploite les informations des correspondances partielles précédentes pour éviter les recomparaisons inutiles, réduisant ainsi la complexité temporelle.

L'élément clé de KMP est le tableau next (ou table de préfixes). Ce tableau, pour un indice i donné, stocke la longueur du plus long préfixe propre de la sous-chaîne needle[0...i] qui est également un suffixe propre de cette même sous-chaîne.

next[i] = j signifie que si une correspondance échoue à l'indice i de needle, la prochaine comparaison doit commencer à l'indice j de needle, en utilisant les informations de préfixe/suffixe déjà trouvées.

Construction du tableau next

La construction du tableau next est essentielle pour l'algorithme KMP. Elle implique le calcul des préfixes et suffixes propres pour la chaîne needle.

Étapes pour construire le tableau next :

1. Initialisation : next[0] est toujours 0 car une chaîne vide n'a pas de préfixe ou de suffixe propre. L'itération commence à partir de i = 1.
2. Traitement des non-correspondances de préfixe/suffixe : Si le caractère courant s[i] ne correspond pas au caractère au point de comparaison s[j], nous devons reculer dans le tableau next (j = next[j - 1]) jusqu'à ce qu'une correspondance soit trouvée ou que j atteigne 0.
3. Traitement des correspondances de préfixe/suffixe : Si s[i] correspond à s[j], nous incrémentons j, indiquant un préfixe/suffixe plus long.

void getNext(int* next, const std::string& s) {
    next[0] = 0; // Le préfixe/suffixe propre le plus long pour une chaîne de longueur 1 est 0.
    for (int i = 1, j = 0; i < s.length(); ++i) {
        // Tant que j > 0 et que les caractères ne correspondent pas,
        // nous reculons en utilisant les informations du tableau next.
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        // Si les caractères correspondent, nous étendons le préfixe/suffixe.
        if (s[i] == s[j]) {
            ++j;
        }
        // Nous stockons la longueur du préfixe/suffixe propre le plus long pour s[0...i].
        next[i] = j;
    }
}

Processus de correspondance KMP

Le processus de correspondance KMP est similaire à la construction du tableau next.

Une fois le tableau next construit, nous parcourons haystack. Si une divergence se produit entre haystack[i] et needle[j], nous utilisons next[j - 1] pour repositionner j, évitant ainsi de recommencer la recherche depuis le début dans haystack.

Lorsqu'une correspondance complète est trouvée (c'est-à-dire lorsque j atteint la longueur de needle), nous renvoyons l'indice de départ de la correspondance dans haystack, qui est i - needle.size() + 1.

int strStr(std::string haystack, std::string needle) {
    if (needle.empty()) {
        return 0; // Une chaîne vide est toujours trouvée au début.
    }
    int n = haystack.length();
    int m = needle.length();
    if (m > n) {
        return -1; // La recherche est impossible si needle est plus longue que haystack.
    }

    int next[m];
    // Appel de la fonction pour calculer le tableau next pour needle.
    // Note : Implémentation de getNext fournie ci-dessus.
    getNext(next, needle); 

    // Processus de correspondance
    for (int i = 0, j = 0; i < n; ++i) {
        // Si une divergence se produit, reculez j en utilisant le tableau next.
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        // Si les caractères correspondent, avancez j.
        if (haystack[i] == needle[j]) {
            ++j;
        }
        // Si j atteint la longueur de needle, une correspondance complète est trouvée.
        if (j == m) {
            return (i - m + 1); // Retourne l'indice de départ de la correspondance.
        }
    }
    return -1; // Aucune correspondance trouvée.
}

Analyse de complexité pour KMP

• Complexité temporelle : O(n + m), où n est la longueur de haystack et m est la longueur de needle. La construction du tableau next prend O(m) et le processus de correspondance prend O(n). Bien que le pointeur j puisse reculer, le nombre total de pas vers l'avant est limité et le nombre total de pas vers l'arrière ne peut pas dépasser le nombre de pas vers l'avant.
• Complexité spatiale : O(m) pour stocker le tableau next.

LeetCode 459 : Chaîne de sous-chaînes répétées

Lien du problème : LeetCode 459. Chaîne de sous-chaînes répétées

Description du problème : Étant donné une chaîne non vide composée uniquement de lettres minuscules, déterminez si elle peut être formée en répétant une de ses sous-chaînes plusieurs fois.

Approche 1 : KMP

L'algorithme KMP peut être appliqué ici en utilisant le tableau next de manière légèrement différente.

Après avoir calculé le tableau next pour la chaîne d'entrée s, considérons la valeur next[n-1], où n est la longueur de s. Cette valeur représente la longueur du plus long préfixe propre de s qui est également un suffixe propre de s.

Si une chaîne s est composée de répétitions d'une sous-chaîne, alors la partie de la chaîne qui n'est pas couverte par le plus long préfixe/suffixe propre doit être la sous-chaîne répétée. La longueur de cette sous-chaîne potentielle serait n - next[n-1].

La condition pour qu'une sous-chaîne répétée existe est que la longueur totale de la chaîne n soit divisible par la longueur de la sous-chaîne potentielle (n - next[n-1]), et que next[n-1] ne soit pas zéro (ce qui impliquerait qu'il n'y a pas de préfixe/suffixe propre, sauf si la chaîne elle-même est la répétition d'une seule lettre).

bool repeatedSubstringPattern(std::string s) {
    int n = s.length();
    if (n == 0) {
        return false;
    }

    int next[n];
    // Appel de la fonction pour calculer le tableau next pour s.
    // Note : Implémentation de getNext fournie ci-dessus.
    getNext(next, s);

    int longestPrefixSuffixLength = next[n - 1];

    // Si le plus long préfixe propre n'est pas zéro, et
    // si la longueur totale de la chaîne est divisible par la longueur
    // de la partie restante après le retrait du préfixe/suffixe propre le plus long,
    // alors la chaîne est composée de répétitions.
    if (longestPrefixSuffixLength != 0 && n % (n - longestPrefixSuffixLength) == 0) {
        return true;
    }

    return false;
}

• Complexité temporelle : O(n), car le calcul du tableau next prend O(n).
• Complexité spatiale : O(n) pour stocker le tableau next.

Approche 2 : Manipulation de chaînes

Une astuce élégante pour résoudre ce problème consiste à construire une nouvelle chaîne en concaténant la chaîne d'origine avec elle-même (s + s). Ensuite, nous examinons cette chaîne doublée, en ignorant le premier et le dernier caractère. Si la chaîne d'origine s peut être trouvée comme sous-chaîne dans cette chaîne modifiée ((s + s).substr(1, 2*n - 2)), cela signifie que s est composée de sous-chaînes répétées.

Exemple : Si s = "abab", alors s + s = "abababab". En retirant le premier et le dernier caractère, on obtient "bababa". La chaîne "abab" est bien présente dans "bababa", indiquant qu'elle est composée de sous-chaînes répétées ("ab").

bool repeatedSubstringPattern(std::string s) {
    std::string doubled_s = s + s;
    // Chercher s dans la chaîne doublée, en commençant la recherche à l'indice 1.
    // Si find ne renvoie pas s.length(), cela signifie que s a été trouvée
    // comme sous-chaîne à une position autre que le début ou la fin complète de s+s,
    // ce qui implique une répétition.
    return doubled_s.find(s, 1) != s.length();
}

• Complexité temporelle : Généralement O(n^2) dans le pire des cas pour la plupart des implémentations de find, bien que des optimisatiosn puissent la rapprocher de O(n).
• Complexité spatiale : O(n) pour créer la chaîne doublée.

En résumé, l'algorithme KMP est un outil puissant pour la recherche de sous-chaînes et l'analyse de motifs répétitifs. Comprendre le concept du tableau next est primordial pour maîtriser ces applications.