Find the First Occurrence in a String

+10

Otrzymujesz dwa ciągi znaków: haystack i needle. Zwróć indeks w haystack, od którego zaczyna się pierwsze wystąpienie needle, licząc od 0. Jeśli needle nigdy nie występuje w haystack, zwróć -1. Napisz algorytm wyszukiwania samodzielnie, zamiast wywoływać wbudowaną funkcję wyszukiwania podciągu, taką jak find lub indexOf.

Funkcja

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

haystackstring: tekst do wyszukania w
needlestring: ciąg znaków, którego należy szukać
Zwracainteger: indeks, pod którym zaczyna się pierwsze wystąpienie wartości needle, lub -1, jeśli jej nie ma

Ograniczenia

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Oba ciągi zawierają wyłącznie małe litery alfabetu angielskiego.
needle może być dłuższe niż haystack. Wtedy nie może się pojawić, a odpowiedzią jest -1.

Przykłady

Wejście: haystack = "bananarama"needle = "ana"
Wyjście: 1
Wyjaśnienie: Litery o indeksach 1, 2 i 3 tworzą wyraz ana. Druga kopia zaczyna się na indeksie 3 i nakłada się na pierwszą, ale odpowiedzią jest pierwsza kopia, więc wynik to 1.

Wejście: haystack = "pineapple"needle = "apples"
Wyjście: -1
Wyjaśnienie: apple zaczyna się na indeksie 4, a haystack kończy się zaraz za nim, więc dla ostatniego s w needle nie ma litery do dopasowania. Nie istnieje pełna kopia apples, więc odpowiedzią jest -1.

Wejście: haystack = "abcabcabd"needle = "abcabd"
Wyjście: 3
Wyjaśnienie: Próba od indeksu 0 pasuje do pięciu liter, abcab, a potem napotyka c, podczas gdy szukany ciąg oczekuje d. Pasujący fragment zaczyna się od indeksu 3 i kończy na ostatnim d.

Pytanie dodatkowe

Czy możesz zwrócić każdy indeks, pod którym zaczyna się needle, uwzględniając także nakładające się wystąpienia, nadal w czasie O(n + m)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Porównywanie needle na każdej pozycji początkowej jest poprawne, ale powolne, gdy dopasowanie prawie się udaje: długie częściowe dopasowanie, które zawodzi blisko końca, jest odrzucane, a następne sprawdzenie zaczyna się od pozycji początkowej i ponownie odczytuje większość tych samych liter. Algorytm Knutha-Morrisa-Pratta pozwala zachować tę pracę. Tabela zbudowana wyłącznie na podstawie needle określa, jaka część nieudanego częściowego dopasowania może być nadal wykorzystana, dzięki czemu skanowanie nigdy nie cofa się w haystack i kończy się w czasie O(n + m).

Sprawdź każdą pozycję początkową

Poprawne, ale nie kończy się na największych testach

Intuicja

Oznaczmy długości jako n dla haystack i m dla needle. Kopia needle może zaczynać się na dowolnym indeksie od 0 do n-m. Sprawdź te pozycje początkowe od lewej do prawej. Dla każdej z nich porównuj needle z haystack litera po literze i zatrzymaj się przy pierwszej różnicy. Pierwsza pozycja początkowa, dla której wszystkie m liter są zgodne, jest wynikiem; sprawdzanie od lewej do prawej gwarantuje, że będzie to pierwsza kopia.

Ostatnia pozycja początkowa to n-m, ponieważ kopia zaczynająca się później wykraczałaby poza koniec haystack. To samo ograniczenie obsługuje przypadek, gdy needle jest dłuższe niż haystack: nie ma żadnej pozycji początkowej do sprawdzenia, a pętla kończy działanie, zwracając -1.

Koszt widać, gdy większość liter jest zgodna. Weźmy haystack składające się z 50,000 liter a oraz needle składające się z 24,999 liter a, po których następuje b. Dla każdej z 25,001 pozycji początkowych porównywanych jest 25,000 liter, zanim algorytm dotrze do b, co daje ponad 6 × 10^8 porównań dla wyniku -1.

Algorytm

Niech n i m oznaczają długości haystack i needle.
Dla każdej wartości start od 0 do n-m ustaw j na 0.
Dopóki j < m i haystack[start + j] jest równe needle[j], zwiększaj j.
Jeśli j osiągnie m, wszystkie litery zostały dopasowane: zwróć start.
Jeśli żadne położenie początkowe nie pasuje, zwróć -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

Intuicja

Zobacz, co pomija algorytm brute force. Podczas wyszukiwania abcabd w abcabcabd próba na indeksie 0 dopasowuje abcab, a potem kończy się niepowodzeniem. Te pięć liter kończy się na ab, a ab to także początek wzorca. Po niezgodności dwie litery kolejnej przydatnej próby są już dopasowane, więc możesz kontynuować od tego samego miejsca w tekście.

Brzeg ciągu to krótszy prefiks, który jest także sufiksem, na przykład ab w abcab. Przed wyszukiwaniem zbuduj tablicę lps, w której lps[i] to długość najdłuższego brzegu needle[0..i]. Dla abcabd wynosi ona [0, 0, 0, 1, 2, 0]. Tablica zależy wyłącznie od wzorca. Zbuduj ją za pomocą tej samej pętli dopasowującej, uruchomionej na wzorcu porównywanym z samym sobą.

Następnie przejrzyj tekst jeden raz i przechowuj k, czyli liczbę dotychczas dopasowanych liter wzorca. Jeśli następna litera jest równa needle[k], k zwiększa się o jeden. Jeśli nie, ustaw k na lps[k-1] i ponownie porównaj tę samą literę. Powtarzaj, aż litery będą zgodne albo k wyniesie 0. Cofnięcie się do brzegu nigdy nie pomija żadnego wystąpienia: każde wystąpienie zaczynające się wewnątrz nieudanej próby musi zaczynać się od brzegu dopasowanego fragmentu, a najpierw sprawdzany jest najdłuższy brzeg. Gdy k osiągnie m, wystąpienie zaczęło się na pozycji i-m+1.

Dlaczego algorytm działa w czasie liniowym: k zwiększa się najwyżej o jeden na każdą literę tekstu, a każde cofnięcie je zmniejsza. Nie może zmniejszyć się więcej razy, niż się zwiększyło, więc skanowanie zajmuje najwyżej 2n kroków, a zbudowanie tablicy najwyżej 2m.

Algorytm

Zbuduj lps: przy k = 0, dla każdego i od 1 do m-1, cofaj się, ustawiając k = lps[k-1], dopóki k > 0 i needle[i] różni się od needle[k]; jeśli są równe, zwiększ k; zapisz lps[i] = k.
Ustaw k z powrotem na 0 i przejdź przez przeszukiwany ciąg, używając indeksu i.
Dopóki k > 0 i haystack[i] różni się od needle[k], ustaw k = lps[k-1].
Jeśli haystack[i] jest równe needle[k], zwiększ k.
Jeśli k jest równe m, zwróć i-m+1. Jeśli pętla się zakończy, zwróć -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

Pułapki i przypadki brzegowe

Większość błędów występuje na końcu tekstu przeszukiwanego lub w pętli awaryjnej.

Pozwolenie, by indeks początkowy dochodził do n-1 zamiast n-m. Gdy koniec tekstu przeszukiwanego dopasuje się do początku wzorca, porównanie odczytuje dane poza końcem haystack, co powoduje błąd indeksu w Pythonie, Javie, Rust i Swift.
Zapominanie, że wzorzec może być dłuższy niż tekst przeszukiwany. W przypadku długości bez znaku, takich jak size_t w C++ lub usize w Rust, n-m nie może być ujemne: C++ zawija tę wartość do ogromnej liczby, a Rust wywołuje panikę w kompilacji debugowej. Najpierw sprawdź m > n albo wykonuj obliczenia na liczbach ze znakiem.
Zapisanie awaryjnego przejścia KMP jako if zamiast while. Podczas wyszukiwania aaa w aabaa znak b wymaga dwóch przejść awaryjnych: z 2 do 1, a potem do 0. Jeśli zatrzymasz się po jednym, k pozostanie równe 1, mimo że b niczego nie dopasowuje, i zgłosisz nieistniejące wystąpienie na indeksie 2.
Cofanie indeksu tekstu przeszukiwanego po niedopasowaniu w KMP. Zmienia się tylko k. Cofnięcie i przywraca najgorszą złożoność O(n · m).
Zwracanie indeksu końca dopasowania albo indeksu liczonego od 1. Wynikiem jest początek, liczony od 0. Indeksy w ciągach znaków w Lua i R zaczynają się od 1, więc odejmij 1 przed zwróceniem wyniku.
Deklarowanie strStr na najwyższym poziomie w PHP. W PHP wielkość liter w nazwach funkcji jest ignorowana, więc nazwa koliduje z wbudowaną funkcją strstr. Z tego powodu kod początkowy w PHP umieszcza funkcję we własnej przestrzeni nazw.

Najczęstsze pytania3

Jaka jest złożoność czasowa znajdowania pierwszego wystąpienia ciągu znaków?

Sprawdzenie każdej pozycji początkowej zajmuje w najgorszym przypadku czas O(n · m), gdzie n i m to długości tekstu i wzorca, oraz wymaga dodatkowej pamięci O(1). Algorytm Knutha-Morrisa-Pratta działa w czasie O(n + m) i wymaga O(m) pamięci na swoją tablicę, niezależnie od liter.

Jak działa tabela prefiksów KMP?

Dla każdego prefiksu wzorca tablica przechowuje długość jego najdłuższego właściwego prefiksu, który jest również sufiksem. Po niezgodności, gdy dopasowano k liter, te k liter stanowią prefiks wzorca, a lps[k-1] określa, ile z nich może rozpoczynać następne możliwe wystąpienie. Dla aabaaab tablica ma postać [0, 1, 0, 1, 2, 2, 3].

Dlaczego nie użyć wbudowanej metody find lub indexOf?

W kodzie produkcyjnym warto używać gotowej funkcji, ponieważ jest przetestowana i szybka. Rekruterzy zadają to pytanie, żeby sprawdzić, czy potrafisz napisać pętlę dopasowującą z prawidłowymi granicami, a typowe pytanie dodatkowe dotyczy sposobu uniknięcia pesymistycznej złożoności O(n · m). Pesymistyczna złożoność wbudowanej funkcji wyszukiwania zależy od języka i wersji biblioteki, więc nie odpowiada na to pytanie dodatkowe.

def strStr(haystack, needle):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

haystack = "bananarama"
needle = "ana"

Oczekiwany wynik