Z-function per la ricerca di pattern
Confrontare i prefissi lungo la stringa
Z-function per la ricerca di pattern è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 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 Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Un altro strumento per la ricerca di corrispondenze
La funzione Z è un'alternativa chiara a KMP per la ricerca di pattern. Molti la trovano più facile da comprendere. ✨
Che cosa significa z[i]
Per ogni indice, z[i] è la lunghezza della sottostringa più lunga che inizia in i e che coincide anche con un prefisso dell'intera stringa.
Un piccolo esempio
Per aabaab, z vale 0,1,0,3,1,0. All'indice 3, la sequenza aab coincide con il prefisso, quindi ha lunghezza 3.
La Z-box
Manteniamo una finestra [l, r], la corrispondenza più a destra trovata finora. Questo ci permette di riutilizzare i confronti precedenti.
l, r = 0, 0All'interno della box
Quando i si trova all'interno della box, copi un valore z già noto per iniziare, limitandolo al bordo della box.
if i < r:
z[i] = min(r - i, z[i - l])Oltre la box
Dopo questo punto di partenza, continui a confrontare i caratteri uno alla volta finché coincidono con il prefisso.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Spostare la box in avanti
Se la corrispondenza arriva più a destra, aggiorni l e r, così gli indici successivi potranno riutilizzarla.
if i + z[i] > r:
l, r = i, i + z[i]Garanzia di tempo lineare
La box si sposta solo verso destra, quindi il lavoro totale è O(n). Ogni carattere contribuisce per una quantità limitata.
Cercare con Z
Concateni pattern + sep + text e calcoli Z. Ogni valore z uguale alla lunghezza del pattern indica una corrispondenza.
combined = pattern + chr(0) + text
z = z_function(combined)Leggere le corrispondenze
Scorra l'array Z: ovunque z[i] == len(pattern), la corrispondenza inizia nel punto corrispondente del testo.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z e KMP
Z e KMP hanno entrambi una complessità lineare. Z è spesso più semplice da implementare, quindi è un'ottima alternativa da tenere nel proprio arsenale.
Verifica rapida
Si assicuri di aver compreso bene il significato dell'array Z.
Riepilogo: la funzione Z vince
Ha costruito l'array Z con una box scorrevole, ha cercato in tempo lineare e ora dispone di una valida alternativa a KMP. 🎯
Domande Frequenti
La lezione «Z-function per la ricerca di pattern» è gratuita?
Sì — il testo completo di «Z-function per la ricerca di pattern» è 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 Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Z-function per la ricerca di pattern»?
Confrontare i prefissi lungo la stringa Eserciti Competitive Programming Academy 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 Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Z-function per la ricerca di pattern»?
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 Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy 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