KMP-prefixfunctie
Een patroon vinden in O(n + m)
KMP-prefixfunctie is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Het probleem van patroonherkenning
Je wilt vinden waar een klein patroon in een grote tekst voorkomt. Naïeve controles zijn traag, dus programmeerwedstrijden belonen een slimmere scan. 🔍
Waarom naïef zoeken traag is
Het patroon op elke positie vergelijken kan O(n*m) tijd kosten. Bij grote invoer overschrijdt dat ongemerkt je tijdslimiet.
Maak kennis met de prefixfunctie
De prefixfunctie meet op elke positie het langste echte prefix dat ook een suffix is. Dit is het hart van KMP.
Echt prefix en suffix
Een echt prefix of suffix sluit de volledige tekenreeks zelf uit. Voor ababa heeft het langste overeenkomende paar lengte 3: aba.
Wat pi[i] opslaat
We slaan de waarden op in een array met de naam pi. Hier is pi[i] de lengte van het langste prefix-suffix voor de deelreeks die op index i eindigt.
pi in één doorgang opbouwen
Je bouwt pi van links naar rechts op en hergebruikt eerdere waarden in plaats van alles opnieuw te controleren. Die hergebruikte informatie is de hele truc.
def prefix_function(s):
pi = [0] * len(s)
return piDe terugval-lus
Als tekens niet overeenkomen, val je terug op pi[k-1] in plaats van terug te gaan naar nul. Zo voorkom je dat je werk opnieuw doet.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Een overeenkomst uitbreiden
Als de huidige tekens overeenkomen, verhoog je de lengte met één en leg je die vast. Niet-overeenkomsten bij nul blijven gewoon nul.
if s[i] == s[k]:
k += 1
pi[i] = kZoeken met deze truc
Als je in een tekst naar een patroon wilt zoeken, plak je ze aan elkaar als pattern + sep + text. Elke pi-waarde die gelijk is aan de patroonlengte markeert een volledige overeenkomst.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Waarom een scheidingsteken belangrijk is
Het scheidingsteken is een symbool dat in geen van beide tekenreeksen voorkomt. Het voorkomt dat overeenkomsten over de samenvoeging heen lopen en valse treffers opleveren.
Winst dankzij lineaire tijd
Zowel het opbouwen als het zoeken draait in O(n + m). Elk teken wordt één keer verwerkt, dus KMP schaalt naar enorme invoer voor programmeerwedstrijden.
Snelle controle
Test je begrip van wat de prefixfunctie vastlegt.
Herhaling: KMP in het kort
Je hebt de prefixfunctie geleerd: bouw pi één keer op, val terug bij niet-overeenkomsten en zoek in lineaire tijd. Dat is KMP in het kort. 🎯
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “KMP-prefixfunctie” gratis?
Ja — de volledige tekst van “KMP-prefixfunctie” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “KMP-prefixfunctie”?
Een patroon vinden in O(n + m) Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “KMP-prefixfunctie”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.