Find the First Occurrence in a String

Q: Qual è la complessità temporale della ricerca della prima occorrenza di una stringa?

Controllare ogni posizione iniziale richiede tempo O(n · m) nel caso peggiore, dove n e m sono le lunghezze della stringa di ricerca e della stringa cercata, e spazio aggiuntivo O(1) . L'algoritmo di Knuth-Morris-Pratt richiede tempo O(n + m) e spazio O(m) per la sua tabella, indipendentemente dalle lettere.

FacileArray e stringhe Due puntatori

+10

Ricevi due stringhe, haystack e needle. Restituisci l’indice in haystack in cui inizia la prima occorrenza di needle, contando da 0. Se needle non compare mai in haystack, restituisci -1. Implementa la ricerca tu stesso, invece di chiamare una funzione di ricerca di sottostringhe integrata come find o indexOf.

Funzione

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

haystackstring: il testo da cercare in
needlestring: la stringa da cercare
Restituisceinteger: l'indice in cui inizia la prima occorrenza di needle, oppure -1 se non ce n'è nessuna

Vincoli

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Entrambe le stringhe contengono solo lettere inglesi minuscole.
needle può essere più lunga di haystack. In tal caso non può essere presente e la risposta è -1.

Esempi

Input: haystack = "bananarama"needle = "ana"
Output: 1
Spiegazione: Le lettere agli indici 1, 2 e 3 formano ana. Una seconda copia inizia all'indice 3 e si sovrappone alla prima, ma la risposta è la prima copia, quindi è 1.

Input: haystack = "pineapple"needle = "apples"
Output: -1
Spiegazione: apple inizia all'indice 4 e l'haystack termina subito dopo, quindi la s finale del needle non ha alcuna lettera con cui corrispondere. Non esiste una copia completa di apples, quindi la risposta è -1.

Input: haystack = "abcabcabd"needle = "abcabd"
Output: 3
Spiegazione: Il tentativo all’indice 0 corrisponde a cinque lettere, abcab, poi incontra una c mentre l’ago si aspetta una d. La copia che funziona inizia all’indice 3 e termina con la d finale.

+16 test nascosti all’invio

Per approfondire

Riesci a restituire ogni indice in cui inizia needle, incluse le occorrenze sovrapposte, sempre in tempo O(n + m)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Confrontare needle a ogni posizione iniziale è corretto, ma lento quando le corrispondenze quasi riescono: una corrispondenza parziale lunga che fallisce verso la fine viene scartata e, all’inizio successivo, si leggono di nuovo quasi le stesse lettere. L’algoritmo di Knuth-Morris-Pratt riutilizza quel lavoro. Una tabella costruita usando solo needle indica quanta parte di una corrispondenza parziale fallita può ancora essere riutilizzata, così la scansione non torna mai indietro in haystack e termina in O(n + m).

Controlla ogni posizione iniziale

Corretto, ma non termina sui test più grandi

Intuizione

Indichiamo con n la lunghezza di haystack e con m quella di needle. Una copia di needle può iniziare a qualsiasi indice da 0 a n-m. Prova queste posizioni iniziali da sinistra a destra. Per ciascuna, confronta needle con haystack lettera per lettera e fermati alla prima differenza. La prima posizione iniziale in cui tutte le m lettere corrispondono è la risposta; procedendo da sinistra a destra, trovi la prima copia.

L'ultima posizione iniziale è n-m, perché una copia che iniziasse più avanti supererebbe la fine di haystack. Lo stesso limite gestisce il caso in cui needle sia più lunga di haystack: non c'è alcuna posizione iniziale da provare e il ciclo termina restituendo -1.

Il costo si nota quando la maggior parte delle lettere corrisponde. Considera un haystack di 50.000 a e un needle composto da 24.999 a seguite da una b. Ciascuna delle 25.001 posizioni iniziali confronta 25.000 lettere prima di raggiungere la b, per un totale di oltre 6 × 10^8 confronti, con risposta -1.

Algoritmo

Siano n e m le lunghezze di haystack e needle.
Per ogni start da 0 a n-m, imposta j a 0.
Mentre j < m e haystack[start + j] è uguale a needle[j], incrementa j.
Se j raggiunge m, tutte le lettere corrispondono: restituisci start.
Se nessun valore di start funziona, restituisci -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

Intuizione

Osserva cosa scarta l’algoritmo di forza bruta. Cercando abcabd in abcabcabd, il tentativo all’indice 0 corrisponde a abcab e poi fallisce. Queste cinque lettere terminano con ab, e ab è anche l’inizio della stringa da cercare. Quindi, dopo la mancata corrispondenza, due lettere del successivo tentativo utile sono già state abbinate e puoi continuare dallo stesso punto nella stringa di ricerca.

Un bordo di una stringa è un prefisso più corto che è anche un suffisso, come ab in abcab. Prima della ricerca, crea una tabella lps in cui lps[i] è la lunghezza del bordo più lungo di needle[0..i]. Per abcabd è [0, 0, 0, 1, 2, 0]. La tabella dipende solo dalla stringa da cercare e si costruisce con lo stesso ciclo di corrispondenza, eseguito confrontando la stringa da cercare con sé stessa.

Poi analizza la stringa di ricerca una volta e mantieni k, il numero di lettere della stringa da cercare abbinate finora. Se la lettera successiva è uguale a needle[k], k aumenta di uno. In caso contrario, imposta k a lps[k-1] e confronta di nuovo la stessa lettera, finché non corrisponde o k è 0. Tornare a un bordo non salta alcuna occorrenza: qualsiasi occorrenza che inizi all’interno del tentativo fallito deve iniziare con un bordo della parte già abbinata, e il bordo più lungo viene provato per primo. Quando k raggiunge m, l’occorrenza è iniziata a i-m+1.

Perché è lineare: k aumenta al massimo di uno per ogni lettera della stringa di ricerca, e ogni ripiego lo diminuisce. Non può diminuire più volte di quante sia aumentato, quindi la scansione richiede al massimo 2n passaggi e la creazione della tabella al massimo 2m.

Algoritmo

Costruisci lps: con k = 0, per ogni i da 1 a m-1, arretra con k = lps[k-1] mentre k > 0 e needle[i] è diverso da needle[k]; se coincidono, incrementa k; memorizza lps[i] = k.
Reimposta k a 0 e percorri l'haystack con l'indice i.
Mentre k > 0 e haystack[i] è diverso da needle[k], imposta k = lps[k-1].
Se haystack[i] è uguale a needle[k], incrementa k.
Se k è uguale a m, restituisci i-m+1. Se il ciclo termina, restituisci -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

Trappole e casi limite

La maggior parte dei bug si trova alla fine del pagliaio o nel ciclo di fallback.

Far avanzare l'inizio fino a n-1 invece che fino a n-m. Quando la fine del pagliaio coincide con l'inizio dell'ago, il confronto legge oltre la fine di haystack, causando un errore di indice in Python, Java, Rust e Swift.
Dimenticare che l'ago può essere più lungo del pagliaio. Con lunghezze senza segno, come size_t in C++ o usize in Rust, n-m non può essere negativo: C++ lo riporta a un numero enorme e Rust va in panic in una build di debug. Controlla prima m > n oppure esegui il calcolo con interi con segno.
Scrivere il fallback di KMP usando un if invece di un while. Cercando aaa in aabaa, la b richiede due fallback, da 2 a 1 e poi a 0. Se ti fermi dopo uno, k resta a 1 anche se b non corrisponde a nulla e segnali una copia all'indice 2 che non esiste.
Decrementare l'indice del pagliaio dopo una mancata corrispondenza in KMP. Cambia solo k. Riportare indietro i ripristina il caso peggiore O(n · m).
Restituire la posizione in cui termina la corrispondenza oppure un indice basato su 1. La risposta è l'inizio, contando da 0. Le stringhe in Lua e R iniziano da 1, quindi sottrai 1 prima di restituire il risultato.
Dichiarare strStr al livello principale in PHP. I nomi delle funzioni in PHP non distinguono tra maiuscole e minuscole, quindi entrano in conflitto con la funzione integrata strstr. Per questo, il codice iniziale PHP racchiude la funzione nel proprio namespace.

Domande frequenti4

Qual è la complessità temporale della ricerca della prima occorrenza di una stringa?

Controllare ogni posizione iniziale richiede tempo O(n · m) nel caso peggiore, dove n e m sono le lunghezze della stringa di ricerca e della stringa cercata, e spazio aggiuntivo O(1). L'algoritmo di Knuth-Morris-Pratt richiede tempo O(n + m) e spazio O(m) per la sua tabella, indipendentemente dalle lettere.

Come funziona la tabella dei prefissi KMP?

Per ogni prefisso dell’ago, la tabella memorizza la lunghezza del suo prefisso proprio più lungo che è anche un suffisso. Dopo una mancata corrispondenza con k lettere abbinate, quelle k lettere sono un prefisso dell’ago e lps[k-1] indica quante di esse possono iniziare la successiva possibile occorrenza. Per aabaaab la tabella è [0, 1, 0, 1, 2, 2, 3].

Perché non usare find o indexOf integrati?

Nel codice di produzione dovresti usarlo, perché è testato e veloce. Gli intervistatori propongono questo problema per vedere se sai scrivere il ciclo di ricerca con i limiti corretti, e la consueta domanda successiva chiede come evitare il caso peggiore O(n · m). Il caso peggiore di una ricerca integrata dipende dal linguaggio e dalla versione della libreria, quindi non risponde a questa domanda successiva.

Riesci a risolverlo con l’hashing invece che con KMP?

Sì, con l’algoritmo di Rabin-Karp. Calcola un hash dell’ago e un hash mobile di ogni finestra di m lettere nel testo, aggiornandolo in tempo costante mentre la finestra scorre. Confronta le lettere una per una solo quando gli hash coincidono. In media, richiede O(n + m) tempo, ma molte collisioni di hash possono riportarlo verso O(n · m).

Python

def strStr(haystack, needle):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

haystack = "bananarama"
needle = "ana"

Atteso