KMP-præfiksfunktion
Find et mønster i O(n + m)
KMP-præfiksfunktion er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Problemet med mønstergenkendelse
Du vil finde ud af, hvor et lille mønster optræder i en stor tekst. Naive tjek er langsomme, så i konkurrencer belønnes en smartere gennemgang. 🔍
Hvorfor naiv søgning er langsom
Hvis du sammenligner mønsteret ved hver position, kan det koste O(n*m) tid. På store input overskrider det ubemærket din tidsgrænse.
Mød præfiksfunktionen
Præfiksfunktionen måler ved hver position længden af det længste ægte præfiks, der også er et suffiks. Den er kernen i KMP.
Ægte præfiks og suffiks
Et ægte præfiks eller suffiks udelader hele strengen. For ababa har det længste matchende par længden 3: aba.
Hvad pi[i] gemmer
Vi gemmer værdierne i en tabel, der hedder pi. Her er pi[i] længden af det længste præfiks-suffiks for udsnittet, der slutter ved indeks i.
Byg pi i ét gennemløb
Du bygger pi fra venstre mod højre og genbruger tidligere værdier i stedet for at kontrollere alt fra bunden igen. Denne genbrug er hele tricket.
def prefix_function(s):
pi = [0] * len(s)
return piTilbagetrækningsløkken
Når tegn ikke matcher, går du tilbage til pi[k-1] i stedet for at nulstille til nul. Så undgår du at udføre arbejdet igen.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Udvid et match
Hvis de aktuelle tegn matcher, øger du længden med én og gemmer den. Hvis tegnene ikke matcher, når længden er nul, forbliver den blot nul.
if s[i] == s[k]:
k += 1
pi[i] = kSøg med tricket
Hvis du vil søge efter et mønster i en tekst, skal du sætte dem sammen som pattern + sep + text. Enhver pi-værdi, der er lig med mønsterets længde, markerer et fuldt match.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Hvorfor et skilletegn er vigtigt
Skilletegnet er et symbol, der ikke findes i nogen af de to strenge. Det forhindrer match i at gå på tværs af sammenføjningen og give falske træffere.
Fordelen ved lineær tid
Både opbygningen og søgningen kører i O(n + m). Hvert tegn behandles én gang, så KMP skalerer til meget store input i konkurrencer.
Hurtigt tjek
Test din forståelse af, hvad præfiksfunktionen gemmer.
Opsummering: KMP kort fortalt
Du har lært præfiksfunktionen: byg pi én gang, gå tilbage ved mismatch, og søg i lineær tid. Det er KMP kort fortalt. 🎯
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “KMP-præfiksfunktion” gratis?
Ja — hele teksten til “KMP-præfiksfunktion” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “KMP-præfiksfunktion”?
Find et mønster i O(n + m) Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “KMP-præfiksfunktion”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.