Leg uit hoe het Knuth-Morris-Pratt algoritme voor het zoeken van substrings werkt.

Het Knuth-Morris-Pratt (KMP) algoritme is ontworpen om een substring in een string te zoeken in lineaire tijd, waarbij herhaalde karaktervergelijkingen worden vermeden.

Het belangrijkste idee is om vooraf voor de substring een prefixfunctie-array (of "π-array") te berekenen, die aangeeft hoeveel tekens overeenkomen met het begin van de substring bij een mislukte vergelijking. Dit stelt je in staat, bij een mismatch, niet terug te keren naar het begin van de originele string, maar de substring te verschuiven met het optimale aantal posities.

Voorbeeld:

• Tekst: "ABABDABACDABABCABAB"
• Op zoek naar de substring: "ABABCABAB"

Het algoritme bouwt eerst de prefixfunctie voor de substring, daarna doorloopt het de tekst en vergelijkt de tekens. Bij een mismatch gebruikt het de prefixfunctie om te bepalen vanaf welk teken van de substring de vergelijking moet worden voortgezet, zonder opnieuw te beginnen.

Dit garandeert een complexiteit van O(n + m), waarbij n de lengte van de tekst is, m de lengte van de substring, en is efficiënter dan de naïeve zoekmethode.