Z-Funktion für Mustersuche
Vergleichen Sie Präfixe im gesamten String
Z-Funktion für Mustersuche ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Ein weiteres Matching-Tool
Die Z-Funktion ist eine klare Alternative zu KMP für die Mustersuche. Viele finden sie leichter verständlich. ✨
Bedeutung von z[i]
Für jeden Index gibt z[i] die Länge des längsten Substrings an, der an i beginnt und zugleich mit einem Präfix des gesamten Strings übereinstimmt.
Ein kleines Beispiel
Für aabaab lautet z 0,1,0,3,1,0. Am Index 3 stimmt die Folge aab mit dem Präfix überein, also beträgt die Länge 3.
Die Z-Box
Wir verfolgen ein Fenster [l, r], also den am weitesten rechts liegenden bisher gefundenen Treffer. Dadurch können wir frühere Vergleiche wiederverwenden.
l, r = 0, 0Innerhalb der Box
Wenn i innerhalb der Box liegt, kopieren Sie zunächst einen bekannten z-Wert, begrenzt durch den rechten Rand der Box.
if i < r:
z[i] = min(r - i, z[i - l])Über die Box hinaus erweitern
Nach diesem Startwert vergleichen Sie Zeichen für Zeichen weiter, solange sie mit dem Präfix übereinstimmen.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Die Box nach rechts verschieben
Wenn Ihr Treffer weiter nach rechts reicht, aktualisieren Sie l und r, damit zukünftige Indizes ihn wiederverwenden können.
if i + z[i] > r:
l, r = i, i + z[i]Garantie für lineare Laufzeit
Die Box bewegt sich nur nach rechts, daher beträgt der Gesamtaufwand O(n). Jedes Zeichen trägt nur einen begrenzten Aufwand bei.
Suchen mit Z
Verketten Sie pattern + sep + text und berechnen Sie Z. Jeder z-Wert, der der Länge des Musters entspricht, bezeichnet einen Treffer.
combined = pattern + chr(0) + text
z = z_function(combined)Treffer ablesen
Durchlaufen Sie das Z-Array. Überall dort, wo z[i] == len(pattern) gilt, beginnt der Treffer an der entsprechenden Position im Text.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z im Vergleich zu KMP
Z und KMP laufen beide in linearer Zeit. Z ist oft einfacher zu programmieren und daher eine hervorragende Alternative in Ihrem Werkzeugkasten.
Kurzer Check
Stellen Sie sicher, dass Sie die Bedeutung des Z-Arrays verstanden haben.
Zusammenfassung: Die Z-Funktion gewinnt
Sie haben das Z-Array mit einer gleitenden Box aufgebaut, in linearer Zeit gesucht und nun eine klare Alternative zu KMP zur Hand. 🎯
Häufig gestellte Fragen
Ist die Lektion „Z-Funktion für Mustersuche“ kostenlos?
Ja — der vollständige Text von „Z-Funktion für Mustersuche“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Z-Funktion für Mustersuche“?
Vergleichen Sie Präfixe im gesamten String Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Z-Funktion für Mustersuche“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- KMP-Präfixfunktion
- Polynomiales String-Hashing
- Z-Funktion für Mustersuche
- Tries für Präfixabfragen