Find the First Occurrence in a String

+10

Du erhältst zwei Zeichenfolgen, haystack und needle. Gib den Index in haystack zurück, an dem das erste Vorkommen von needle beginnt, wobei ab 0 gezählt wird. Wenn needle nie in haystack vorkommt, gib -1 zurück. Implementiere die Suche selbst, anstatt eine eingebaute Teilzeichenfolgensuche wie find oder indexOf aufzurufen.

Funktion

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

haystackstring: der zu durchsuchende Text
needlestring: die zu suchende Zeichenfolge
Gibt zurückinteger: der Index, an dem das erste Vorkommen von needle beginnt, oder -1, falls es keines gibt

Einschränkungen

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Beide Zeichenketten enthalten nur englische Kleinbuchstaben.
needle kann länger als haystack sein. Dann kann es nicht darin vorkommen, und die Antwort lautet -1.

Beispiele

Eingabe: haystack = "bananarama"needle = "ana"
Ausgabe: 1
Erklärung: Die Buchstaben an den Indizes 1, 2 und 3 ergeben ana. Eine zweite Kopie beginnt bei Index 3 und überlappt die erste, aber die Antwort ist die erste Kopie, also ist sie 1.

Eingabe: haystack = "pineapple"needle = "apples"
Ausgabe: -1
Erklärung: apple beginnt bei Index 4, und der Heuhaufen endet direkt danach, sodass das abschließende s des Suchworts keinen Buchstaben zum Abgleichen hat. Es gibt kein vollständiges Vorkommen von apples, also lautet die Antwort -1.

Eingabe: haystack = "abcabcabd"needle = "abcabd"
Ausgabe: 3
Erklärung: Der Versuch an Index 0 stimmt mit fünf Buchstaben überein, abcab, trifft dann auf ein c, obwohl die Suchzeichenfolge ein d erwartet. Die passende Übereinstimmung beginnt bei Index 3 und endet mit dem letzten d.

Weiterführende Frage

Kannst du jeden Index zurückgeben, an dem needle beginnt, einschließlich überlappender Vorkommen, und das weiterhin in O(n + m) Zeit?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

needle an jeder Startposition zu vergleichen ist zwar korrekt, aber langsam, wenn Treffer beinahe gelingen: Ein langer Teiltreffer, der kurz vor seinem Ende scheitert, wird verworfen, und beim nächsten Start werden die meisten derselben Buchstaben erneut gelesen. Der Knuth-Morris-Pratt-Algorithmus nutzt diese Arbeit weiter. Eine allein aus needle erstellte Tabelle gibt an, welcher Teil eines fehlgeschlagenen Teiltreffers noch verwendet werden kann. Dadurch bewegt sich die Suche in haystack nie rückwärts und läuft in O(n + m).

Prüfe jede Startposition

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Nennen wir die Längen n für haystack und m für needle. Eine Kopie von needle kann an jedem Index von 0 bis n-m beginnen. Probiere diese Startpositionen von links nach rechts aus. Vergleiche an jeder Position needle Buchstabe für Buchstabe mit haystack und brich beim ersten Unterschied ab. Die erste Startposition, an der alle m Buchstaben übereinstimmen, ist die Antwort, und durch die Suche von links nach rechts ist es die erste Kopie.

Die letzte Startposition ist n-m, weil eine später beginnende Kopie über das Ende von haystack hinausreichen würde. Dieselbe Grenze deckt den Fall ab, dass needle länger als haystack ist: Es gibt keine Startposition zum Ausprobieren, und die Schleife läuft bis zu -1 durch.

Die Kosten zeigen sich, wenn die meisten Buchstaben übereinstimmen. Nehmen wir einen haystack aus 50.000 as und ein needle aus 24.999 as, gefolgt von einem b. An jeder der 25.001 Startpositionen werden 25.000 Buchstaben verglichen, bevor das b erreicht wird. Das sind über 6 × 10^8 Vergleiche für eine Antwort von -1.

Algorithmus

Seien n und m die Längen von haystack und needle.
Setze für jedes start von 0 bis n-m j auf 0.
Erhöhe j, solange j < m gilt und haystack[start + j] gleich needle[j] ist.
Wenn j m erreicht hat, stimmt jeder Buchstabe überein: Gib start zurück.
Wenn kein Startwert funktioniert, gib -1 zurück.

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

Idee

Sieh dir an, was die Brute-Force-Suche verwirft. Bei der Suche nach abcabd in abcabcabd stimmt der Versuch bei Index 0 mit abcab überein und scheitert dann. Diese fünf Buchstaben enden mit ab, und ab ist auch der Anfang des Suchmusters. Nach dem Fehlschlag stimmen also bereits zwei Buchstaben des nächsten sinnvollen Versuchs überein, und du kannst an derselben Stelle im Suchtext weitermachen.

Ein Rand eines Strings ist ein kürzeres Präfix, das zugleich ein Suffix ist, wie ab in abcab. Erstelle vor der Suche eine Tabelle lps, in der lps[i] die Länge des längsten Rands von needle[0..i] ist. Für abcabd lautet sie [0, 0, 0, 1, 2, 0]. Die Tabelle hängt nur vom Suchmuster ab. Du erstellst sie mit derselben Vergleichsschleife, die auf das Suchmuster angewendet wird, um es mit sich selbst zu vergleichen.

Durchsuche dann den Suchtext einmal und behalte k bei, die Anzahl der bisher übereinstimmenden Buchstaben des Suchmusters. Wenn der nächste Buchstabe gleich needle[k] ist, wird k um eins erhöht. Wenn nicht, setze k auf lps[k-1] und vergleiche denselben Buchstaben erneut, bis er übereinstimmt oder k 0 ist. Das Zurückgehen auf einen Rand überspringt niemals ein Vorkommen: Jedes Vorkommen, das innerhalb des fehlgeschlagenen Versuchs beginnt, muss mit einem Rand des bereits abgeglichenen Teils beginnen, und zuerst wird der längste Rand ausprobiert. Wenn k m erreicht, hat das Vorkommen bei i-m+1 begonnen.

Warum das Verfahren linear ist: k steigt pro Buchstabe des Suchtexts höchstens um eins, und bei jedem Zurückgehen sinkt es. Es kann nicht öfter sinken, als es gestiegen ist. Daher benötigt das Durchsuchen höchstens 2n Schritte, und das Erstellen der Tabelle höchstens 2m.

Algorithmus

Erstelle lps: Setze k = 0 und gehe für jedes i von 1 bis m-1 wie folgt vor: Setze k = lps[k-1], solange k > 0 und needle[i] sich von needle[k] unterscheidet. Wenn sie übereinstimmen, erhöhe k. Speichere lps[i] = k.
Setze k auf 0 zurück und durchlaufe den Haystack mit dem Index i.
Solange k > 0 und haystack[i] sich von needle[k] unterscheidet, setze k = lps[k-1].
Wenn haystack[i] gleich needle[k] ist, erhöhe k.
Wenn k gleich m ist, gib i-m+1 zurück. Wenn die Schleife endet, gib -1 zurück.

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

Stolperfallen und Grenzfälle

Die meisten Fehler liegen am Ende des Heuhaufens oder in der Rückfallschleife.

Den Start bis n-1 statt bis n-m laufen lassen. Sobald das Ende des Heuhaufens mit dem Anfang der Nadel übereinstimmt, liest der Vergleich über das Ende von haystack hinaus. Das führt in Python, Java, Rust und Swift zu einem Indexfehler.
Vergessen, dass die Nadel länger als der Heuhaufen sein kann. Bei vorzeichenlosen Längen wie size_t in C++ oder usize in Rust kann n-m nicht negativ werden: C++ lässt den Wert zu einer riesigen Zahl überlaufen, und Rust löst in einem Debug-Build eine Panic aus. Prüfe zuerst m > n oder rechne mit vorzeichenbehafteten Ganzzahlen.
Den KMP-Rückfall als if statt als while schreiben. Bei der Suche nach aaa in aabaa sind für b zwei Rückfälle nötig: von 2 auf 1 auf 0. Wird nach nur einem Rückfall abgebrochen, bleibt k bei 1, obwohl b zu nichts passt, und du meldest eine Kopie an Index 2, die nicht existiert.
Bei einem Nichtübereinstimmen in KMP den Heuhaufen-Index zurücksetzen. Nur k ändert sich. Wenn du i zurücksetzt, entsteht wieder der Worst Case O(n · m).
Die Position zurückgeben, an der die Übereinstimmung endet, oder einen 1-basierten Index. Die Antwort ist der Start, gezählt ab 0. Lua- und R-Strings beginnen bei 1, ziehe also vor der Rückgabe 1 ab.
strStr auf oberster Ebene in PHP deklarieren. Bei PHP wird bei Funktionsnamen nicht zwischen Groß- und Kleinschreibung unterschieden, daher kommt es zu einem Konflikt mit der eingebauten Funktion strstr. Aus diesem Grund stellt der PHP-Code zum Einstieg die Funktion in einen eigenen Namensraum.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität beim Finden des ersten Vorkommens eines Strings?

Das Überprüfen jeder Startposition benötigt im schlimmsten Fall O(n · m) Zeit, wobei n und m die Längen des Heuhaufens und der Nadel sind, und O(1) zusätzlichen Speicherplatz. Der Knuth-Morris-Pratt-Algorithmus benötigt O(n + m) Zeit und O(m) Speicherplatz für seine Tabelle, unabhängig davon, welche Buchstaben vorkommen.

Wie funktioniert die KMP-Präfixtabelle?

Für jedes Präfix des Suchmusters speichert die Tabelle die Länge seines längsten echten Präfixes, das zugleich ein Suffix ist. Nach einem Nichtübereinstimmen, wenn k Buchstaben übereinstimmen, bilden diese k Buchstaben ein Präfix des Suchmusters, und lps[k-1] gibt an, wie viele davon den Anfang des nächsten möglichen Vorkommens bilden können. Für aabaaab lautet die Tabelle [0, 1, 0, 1, 2, 2, 3].

Warum nicht das integrierte <code>find</code> oder <code>indexOf</code> verwenden?

Im Produktivcode solltest du das tun, da es getestet und schnell ist. In Vorstellungsgesprächen wird diese Aufgabe gestellt, um zu sehen, ob du die passende Schleife mit den richtigen Grenzen schreiben kannst. Die übliche Anschlussfrage lautet, wie sich der Worst Case von O(n · m) vermeiden lässt. Der Worst Case einer integrierten Suchfunktion hängt von der Sprache und der Bibliotheksversion ab und beantwortet diese Anschlussfrage daher nicht.

def strStr(haystack, needle):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

haystack = "bananarama"
needle = "ana"

Erwartete Ausgabe