KMP-Präfixfunktion
Finden Sie ein Muster in O(n + m)
KMP-Präfixfunktion ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem des Mustervergleichs
Sie möchten herausfinden, an welcher Stelle ein kleines Muster in einem großen Text vorkommt. Naive Prüfungen sind langsam, daher belohnen Wettbewerbe einen intelligenteren Durchlauf. 🔍
Warum die naive Suche langsam ist
Wenn Sie das Muster an jeder Position vergleichen, kann das O(n*m) Zeit kosten. Bei großen Eingaben überschreiten Sie damit unbemerkt das Zeitlimit.
Die Präfixfunktion kennenlernen
Die Präfixfunktion misst an jeder Position die Länge des längsten echten Präfixes, das zugleich ein Suffix ist. Sie bildet den Kern von KMP.
Echter Präfix und echtes Suffix
Ein echter Präfix oder ein echtes Suffix schließt die gesamte Zeichenkette selbst aus. Für ababa hat das längste übereinstimmende Paar die Länge 3: aba.
Was pi[i] speichert
Wir speichern die Werte in einem Array namens pi. Hier ist pi[i] die Länge des längsten Präfix-Suffixes für den bei Index i endenden Ausschnitt.
pi in einem Durchlauf aufbauen
Sie bauen pi von links nach rechts auf und verwenden frühere Werte wieder, statt von vorn zu beginnen. Diese Wiederverwendung ist der entscheidende Trick.
def prefix_function(s):
pi = [0] * len(s)
return piDie Rückfallschleife
Wenn Zeichen nicht übereinstimmen, greifen Sie auf pi[k-1] zurück, statt den Wert auf null zu setzen. Dadurch vermeiden Sie doppelte Arbeit.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Eine Übereinstimmung erweitern
Wenn die aktuellen Zeichen übereinstimmen, erhöhen Sie die Länge um eins und speichern sie. Nichtübereinstimmungen bei null bleiben einfach null.
if s[i] == s[k]:
k += 1
pi[i] = kMit dem Trick suchen
Um einen Text nach einem Muster zu durchsuchen, verketten Sie beide als pattern + sep + text. Jeder pi-Wert, der der Länge des Musters entspricht, kennzeichnet eine vollständige Übereinstimmung.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Warum ein Trennzeichen wichtig ist
Das Trennzeichen ist ein Symbol, das in keiner der beiden Zeichenketten vorkommt. Es verhindert, dass Übereinstimmungen über die Verbindung hinwegreichen und falsche Treffer erzeugen.
Der Vorteil der linearen Laufzeit
Sowohl der Aufbau als auch die Suche laufen in O(n + m). Jedes Zeichen wird einmal verarbeitet, daher skaliert KMP auch für sehr große Wettbewerbseingaben.
Schnelltest
Testen Sie, wie gut Sie verstanden haben, was die Präfixfunktion speichert.
Rückblick: KMP kompakt
Sie haben die Präfixfunktion kennengelernt: pi einmal aufbauen, bei Nichtübereinstimmungen zurückfallen und in linearer Zeit suchen. Das ist KMP kompakt erklärt. 🎯
Häufig gestellte Fragen
Ist die Lektion „KMP-Präfixfunktion“ kostenlos?
Ja — der vollständige Text von „KMP-Präfixfunktion“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „KMP-Präfixfunktion“?
Finden Sie ein Muster in O(n + m) Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 1 von 4.
Wie lange dauert die Lektion „KMP-Präfixfunktion“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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.