Z-functie voor patroonzoeken

De Z-functie is een helder alternatief voor KMP bij het zoeken naar patronen. Veel mensen vinden de redenering ermee eenvoudiger. ✨

Voor elke index is z[i] de lengte van de langste deelreeks die op i begint en ook overeenkomt met een voorvoegsel van de hele tekenreeks.

Voor aabaab is z gelijk aan 0,1,0,3,1,0. Op index 3 komt de reeks aab overeen met het voorvoegsel, dus is de lengte 3.

We houden een venster [l, r] bij: de meest rechtse overeenkomst die we tot nu toe hebben gevonden. Zo kunnen we eerdere vergelijkingen hergebruiken.

Als i binnen het venster ligt, kopieer je een bekende z-waarde als startpunt, begrensd door de rand van het venster.

Na het startpunt blijf je tekens één voor één vergelijken, zolang ze overeenkomen met het voorvoegsel.

Als je overeenkomst verder naar rechts reikt, werk je l en r bij, zodat toekomstige indices de overeenkomst kunnen hergebruiken.

Het venster beweegt alleen naar rechts, dus de totale hoeveelheid werk is O(n). Elk teken draagt een begrensde hoeveelheid werk bij.

Voeg pattern + sep + text samen en voer Z uit. Elke z-waarde die gelijk is aan de lengte van het patroon, is een overeenkomst.

Doorloop de Z-reeks; waar z[i] == len(pattern) geldt, begint de overeenkomst op de bijbehorende plek in de tekst.

Z en KMP werken allebei in lineaire tijd. Z is vaak eenvoudiger te programmeren en is daarom een uitstekend alternatief in je gereedschapskist.

Je hebt de Z-reeks met een schuivend venster opgebouwd, in lineaire tijd gezocht en hebt nu een helder alternatief voor KMP. 🎯