Funzione prefissa KMP
Trovare un pattern in O(n + m)
Funzione prefissa KMP è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il problema della ricerca di pattern
Si vuole trovare dove compare un piccolo pattern all'interno di un testo grande. I controlli ingenui sono lenti, quindi nelle gare conviene una scansione più intelligente. 🔍
Perché la ricerca ingenua è lenta
Confrontare il pattern in ogni posizione può costare O(n*m) in termini di tempo. Su input grandi questo può superare inavvertitamente il limite di tempo.
Presentiamo la funzione prefisso
La funzione prefisso misura, in ogni posizione, il prefisso proprio più lungo che è anche un suffisso. È il cuore di KMP.
Prefisso proprio e suffisso
Un prefisso o suffisso proprio non comprende l'intera stringa. Per ababa, la coppia corrispondente più lunga ha lunghezza 3: aba.
Che cosa memorizza pi[i]
Si memorizzano i valori in un array chiamato pi. Qui pi[i] è la lunghezza del prefisso-suffisso più lungo per la porzione che termina all'indice i.
Costruire pi in un'unica scansione
Si costruisce pi da sinistra a destra, riutilizzando i valori precedenti invece di ricontrollare tutto da zero. Questo riutilizzo è l'intero trucco.
def prefix_function(s):
pi = [0] * len(s)
return piIl ciclo di ripiego
Quando i caratteri non corrispondono, si torna a pi[k-1] invece di reimpostare a zero. In questo modo si evita di ripetere il lavoro.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Estendere una corrispondenza
Se i caratteri correnti corrispondono, si aumenta di uno la lunghezza e si registra il risultato. Le non corrispondenze quando si è a zero restano semplicemente a zero.
if s[i] == s[k]:
k += 1
pi[i] = kCercare con il trucco
Per cercare un pattern nel testo, si concatenano come pattern + sep + text. Qualsiasi valore di pi uguale alla lunghezza del pattern indica una corrispondenza completa.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Perché serve un separatore
Il separatore è un simbolo che non compare in nessuna delle due stringhe. Impedisce alle corrispondenze di attraversare la concatenazione e produrre risultati falsi.
Il vantaggio del tempo lineare
Sia la costruzione sia la ricerca hanno complessità O(n + m). Ogni carattere viene elaborato una volta, quindi KMP è adatto a input enormi nelle gare.
Verifica rapida
Verifichi di aver compreso che cosa registra la funzione prefisso.
Riepilogo: KMP in breve
Ha imparato la funzione prefisso: si costruisce pi una volta, si torna indietro in caso di non corrispondenza e si cerca in tempo lineare. Questo è KMP in breve. 🎯
Domande Frequenti
La lezione «Funzione prefissa KMP» è gratuita?
Sì — il testo completo di «Funzione prefissa KMP» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Funzione prefissa KMP»?
Trovare un pattern in O(n + m) Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Funzione prefissa KMP»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Funzione prefissa KMP
- Hashing polinomiale delle stringhe
- Z-function per la ricerca di pattern
- Trie per le ricerche sui prefissi