Funkcja Z do wyszukiwania wzorców

Funkcja Z jest przejrzystą alternatywą dla KMP podczas wyszukiwania wzorców. Wielu programistów uważa, że łatwiej o niej myśleć. ✨

Dla każdego indeksu z[i] oznacza długość najdłuższego podnapisu zaczynającego się w i, który jest jednocześnie zgodny z prefiksem całego napisu.

Dla aabaab tablica z ma wartości 0,1,0,3,1,0. W indeksie 3 fragment aab pasuje do prefiksu, więc jego długość wynosi 3.

Śledzimy okno [l, r], czyli najbardziej wysunięte w prawo znalezione dopasowanie. Dzięki temu można ponownie wykorzystać wcześniejsze porównania.

Gdy i znajduje się wewnątrz przedziału, można na początek skopiować znaną wartość z, ograniczając ją do prawego końca przedziału.

Po takim wstępnym dopasowaniu należy nadal porównywać znaki jeden po drugim, dopóki pasują do prefiksu.

Jeśli dopasowanie sięga dalej w prawo, należy zaktualizować l i r, aby przyszłe indeksy mogły je ponownie wykorzystać.

Przedział przesuwa się wyłącznie w prawo, więc całkowity nakład pracy wynosi O(n). Każdy znak wnosi ograniczoną ilość pracy.

Należy połączyć pattern + sep + text i obliczyć funkcję Z. Każda wartość z równa długości wzorca oznacza dopasowanie.

Należy przejrzeć tablicę Z; wszędzie tam, gdzie z[i] == len(pattern), dopasowanie zaczyna się w odpowiadającym miejscu tekstu.

Z i KMP działają w czasie liniowym. Funkcja Z jest często prostsza do zakodowania, więc stanowi świetną alternatywę w zestawie narzędzi.

Należy upewnić się, że znaczenie tablicy Z jest dobrze utrwalone.

Można już budować tablicę Z za pomocą przesuwanego przedziału, wyszukiwać w czasie liniowym i korzystać z przejrzystej alternatywy dla KMP. 🎯