KMP:s prefixfunktion
Hitta ett mönster i O(n + m)
KMP:s prefixfunktion är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet med mönstermatchning
Du vill hitta var ett litet mönster förekommer i en stor text. Naiva kontroller är långsamma, så programmeringstävlingar belönar en smartare genomsökning. 🔍
Varför naiv sökning är långsam
Att jämföra mönstret vid varje position kan kosta O(n*m) i körtid. För stora indata överskrider det lätt tidsgränsen.
Möt prefixfunktionen
Prefixfunktionen mäter vid varje position längden på det längsta äkta prefix som också är ett suffix. Den är kärnan i KMP.
Äkta prefix och suffix
Ett äkta prefix eller suffix får inte vara hela strängen i sig. För ababa har det längsta matchande paret längden 3: aba.
Vad pi[i] lagrar
Vi lagrar värdena i en array som kallas pi. Här är pi[i] längden på det längsta prefixet och suffixet för delsträngen som slutar vid index i.
Bygg pi i en genomgång
Du bygger pi från vänster till höger och återanvänder tidigare värden i stället för att kontrollera allt från början. Det är hela tricket.
def prefix_function(s):
pi = [0] * len(s)
return piÅtergångsloopen
När tecknen inte matchar går du tillbaka till pi[k-1] i stället för att återställa till noll. Då undviker du att göra om arbete.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Förläng en matchning
Om de aktuella tecknen matchar ökar du längden med ett och lagrar resultatet. Om tecknen inte matchar när längden är noll förblir den noll.
if s[i] == s[k]:
k += 1
pi[i] = kSök med tricket
För att söka efter ett mönster i en text sätter du ihop dem som pattern + sep + text. Alla pi-värden som är lika med mönstrets längd markerar en fullständig träff.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Varför en separator behövs
Separatorn är ett tecken som inte finns i någon av strängarna. Den hindrar matchningar från att läcka över skarven och ge falska träffar.
Vinsten med linjär tid
Både uppbyggnad och sökning körs på O(n + m). Varje tecken behandlas en gång, så KMP fungerar även för mycket stora indata i tävlingar.
Snabb kontroll
Testa hur väl du förstått vad prefixfunktionen lagrar.
Sammanfattning: KMP i korthet
Du har lärt dig prefixfunktionen: bygg pi en gång, gå tillbaka vid felmatchningar och sök i linjär tid. Det är KMP i korthet. 🎯
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”KMP:s prefixfunktion” gratis?
Ja – hela texten till ”KMP:s prefixfunktion” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”KMP:s prefixfunktion”?
Hitta ett mönster i O(n + m) Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”KMP:s prefixfunktion”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- KMP:s prefixfunktion
- Polynomiell stränghashning
- Z-funktion för mönstersökning
- Träd för prefixuppslag