Find the First Occurrence in a String

Q: Quelle est la complexité temporelle de la recherche de la première occurrence d’une chaîne de caractères ?

Vérifier chaque position de départ prend un temps de O(n · m) dans le pire des cas, où n et m sont les longueurs du texte et du motif, ainsi qu’un espace supplémentaire de O(1) . L’algorithme de Knuth-Morris-Pratt prend un temps de O(n + m) et un espace de O(m) pour sa table, quelles que soient les lettres.

FacileTableaux et chaînes Deux pointeurs

+10

Vous obtenez deux chaînes, haystack et needle. Renvoyez l’indice dans haystack où commence la première occurrence de needle, en comptant à partir de 0. Si needle n’apparaît jamais dans haystack, renvoyez -1. Écrivez vous-même la recherche au lieu d’appeler une fonction intégrée de recherche de sous-chaîne telle que find ou indexOf.

Fonction

strStr(haystack: string, needle: string) → integer

haystackstring: le texte à rechercher dans
needlestring: la chaîne à rechercher
Renvoieinteger: l’index où commence la première occurrence de needle, ou -1 s’il n’y en a aucune

Contraintes

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Les deux chaînes contiennent uniquement des lettres minuscules de l’alphabet anglais.
needle peut être plus long que haystack. Il ne peut alors pas apparaître, et la réponse est -1.

Exemples

Entrée: haystack = "bananarama"needle = "ana"
Sortie: 1
Explication: Les lettres aux indices 1, 2 et 3 forment ana. Une deuxième occurrence commence à l’indice 3 et chevauche la première, mais la réponse est la première occurrence, donc c’est 1.

Entrée: haystack = "pineapple"needle = "apples"
Sortie: -1
Explication: apple commence à l’index 4, et la chaîne se termine juste après, donc le s final de la chaîne recherchée n’a aucune lettre à laquelle correspondre. Il n’existe aucune copie complète de apples, donc la réponse est -1.

Entrée: haystack = "abcabcabd"needle = "abcabd"
Sortie: 3
Explication: La tentative à l’index 0 correspond à cinq lettres, abcab, puis rencontre un c alors que l’aiguille attend un d. La copie qui fonctionne commence à l’index 3 et se termine par le d final.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer chaque index où needle commence, y compris les occurrences qui se chevauchent, toujours en O(n + m) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Comparer needle à chaque position de départ est correct, mais lent lorsque les correspondances échouent presque : une longue correspondance partielle qui échoue près de la fin est abandonnée, et la recherche suivante relit la plupart des mêmes lettres. L’algorithme de Knuth-Morris-Pratt conserve ce travail. Une table construite uniquement à partir de needle indique quelle partie d’une correspondance partielle échouée peut encore être utilisée, de sorte que le balayage ne revient jamais en arrière dans haystack et s’achève en O(n + m).

Vérifiez chaque position de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Appelons n la longueur de haystack et m celle de needle. Une copie de needle peut commencer à n’importe quel indice de 0 à n-m. Essayez ces positions de départ de gauche à droite. Pour chacune, comparez needle à haystack lettre par lettre et arrêtez-vous à la première différence. La première position de départ où les m lettres correspondent toutes est la réponse, et en procédant de gauche à droite, vous trouvez la première copie.

La dernière position de départ est n-m, car une copie qui commencerait plus loin dépasserait la fin de haystack. Cette même limite s’applique lorsque needle est plus long que haystack : il n’y a aucune position de départ à essayer, et la boucle se termine en renvoyant -1.

Le coût apparaît lorsque la plupart des lettres correspondent. Prenez un haystack de 50,000 a et un needle composé de 24,999 a suivis d’un b. Chacune des 25,001 positions de départ compare 25,000 lettres avant d’arriver au b, ce qui représente plus de 6 × 10^8 comparaisons pour une réponse de -1.

Algorithme

Soient n et m les longueurs de haystack et needle.
Pour chaque start de 0 à n-m, définissez j à 0.
Tant que j < m et que haystack[start + j] est égal à needle[j], incrémentez j.
Si j atteint m, toutes les lettres correspondent : renvoyez start.
Si aucun départ ne fonctionne, renvoyez -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

Intuition

Regardez ce que la force brute laisse de côté. En recherchant abcabd dans abcabcabd, la tentative à l’index 0 correspond à abcab, puis échoue. Ces cinq lettres se terminent par ab, et ab est aussi le début du motif. Ainsi, après l’échec de la correspondance, deux lettres de la prochaine tentative utile sont déjà correspondantes, et vous pouvez continuer au même endroit dans le texte.

Un bord d’une chaîne est un préfixe plus court qui est aussi un suffixe, comme ab dans abcab. Avant la recherche, construisez une table lps où lps[i] est la longueur du plus long bord de needle[0..i]. Pour abcabd, elle vaut [0, 0, 0, 1, 2, 0]. La table dépend uniquement du motif, et vous la construisez avec la même boucle de correspondance, appliquée au motif lui-même.

Parcourez ensuite le texte une seule fois et conservez k, le nombre de lettres du motif déjà correspondantes. Si la lettre suivante est égale à needle[k], k augmente de un. Sinon, définissez k sur lps[k-1] et comparez de nouveau la même lettre, jusqu’à ce qu’elle corresponde ou que k soit égal à 0. Revenir à un bord ne fait jamais sauter une occurrence : toute occurrence commençant à l’intérieur de la tentative échouée doit commencer par un bord de la partie déjà correspondante, et le bord le plus long est essayé en premier. Quand k atteint m, l’occurrence a commencé à i-m+1.

Pourquoi cette méthode est linéaire : k augmente d’au plus un pour chaque lettre du texte, et chaque retour le fait diminuer. Il ne peut pas diminuer plus de fois qu’il n’a augmenté, donc le parcours prend au plus 2n étapes, et la construction de la table en prend au plus 2m.

Algorithme

Construisez lps : avec k = 0, pour chaque i de 1 à m-1, revenez en arrière avec k = lps[k-1] tant que k > 0 et que needle[i] diffère de needle[k] ; si elles correspondent, augmentez k ; stockez lps[i] = k.
Réinitialisez k à 0 et parcourez la chaîne principale avec l’indice i.
Tant que k > 0 et que haystack[i] diffère de needle[k], définissez k = lps[k-1].
Si haystack[i] est égal à needle[k], augmentez k.
Si k est égal à m, renvoyez i-m+1. Si la boucle se termine, renvoyez -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

Pièges et cas limites

La plupart des bogues se trouvent à la fin du texte recherché ou dans la boucle de repli.

Faire aller le début jusqu’à n-1 au lieu de n-m. Lorsque la fin du texte recherché correspond au début du motif, la comparaison lit au-delà de la fin de haystack, ce qui provoque une erreur d’indice dans Python, Java, Rust et Swift.
Oublier que le motif peut être plus long que le texte recherché. Avec des longueurs non signées, comme size_t en C++ ou usize en Rust, n-m ne peut pas être négatif : C++ le fait déborder jusqu’à une valeur énorme, et Rust déclenche une panique dans une compilation de débogage. Vérifie d’abord m > n, ou effectue le calcul avec des entiers signés.
Écrire le repli KMP avec un if plutôt qu’un while. En recherchant aaa dans aabaa, le b nécessite deux replis, de 2 à 1 puis à 0. Si tu t’arrêtes après un seul repli, k reste à 1 alors que rien ne correspond à b, et tu signales une occurrence à l’indice 2 qui n’existe pas.
Reculer l’indice du texte recherché après une discordance avec KMP. Seul k change. Reculer i réintroduit le pire cas en O(n · m).
Renvoyer la position où la correspondance se termine, ou un indice à partir de 1. La réponse est le début, compté à partir de 0. Les chaînes Lua et R commencent à 1 : soustrais donc 1 avant de renvoyer le résultat.
Déclarer strStr au niveau supérieur en PHP. Les noms de fonction PHP ne distinguent pas les majuscules des minuscules, ce qui crée un conflit avec la fonction intégrée strstr. Pour cette raison, le code de départ PHP place la fonction dans son propre espace de noms.

Questions fréquentes4

Quelle est la complexité temporelle de la recherche de la première occurrence d’une chaîne de caractères ?

Vérifier chaque position de départ prend un temps de O(n · m) dans le pire des cas, où n et m sont les longueurs du texte et du motif, ainsi qu’un espace supplémentaire de O(1). L’algorithme de Knuth-Morris-Pratt prend un temps de O(n + m) et un espace de O(m) pour sa table, quelles que soient les lettres.

Comment fonctionne la table des préfixes KMP ?

Pour chaque préfixe du motif, le tableau stocke la longueur de son plus long préfixe propre qui est également un suffixe. Après une incompatibilité alors que k lettres ont été mises en correspondance, ces k lettres forment un préfixe du motif, et lps[k-1] indique combien d’entre elles peuvent commencer la prochaine occurrence possible. Pour aabaaab, le tableau est [0, 1, 0, 1, 2, 2, 3].

Pourquoi ne pas utiliser les méthodes intégrées find ou indexOf ?

Dans le code de production, tu devrais utiliser cette méthode, car elle est testée et rapide. Les recruteurs posent cette question pour voir si tu sais écrire la boucle de recherche correspondante avec des bornes correctes, et la question complémentaire habituelle porte sur la manière d’éviter le pire cas O(n · m). Le pire cas d’une recherche intégrée dépend du langage et de la version de la bibliothèque ; elle ne répond donc pas à cette question complémentaire.

Peux-tu le résoudre avec le hachage au lieu de KMP ?

Oui, avec l’algorithme de Rabin-Karp. Calculez le hachage de l’aiguille et un hachage glissant de chaque fenêtre de m lettres dans le texte, en le mettant à jour en temps constant à mesure que la fenêtre se déplace. Comparez les lettres une à une uniquement lorsque les hachages concordent. L’algorithme s’exécute en temps attendu O(n + m), mais de nombreuses collisions de hachage peuvent le rapprocher de O(n · m).

Python

def strStr(haystack, needle):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

haystack = "bananarama"
needle = "ana"

Attendu