Funkcja Z do wyszukiwania wzorców
Dopasowywanie prefiksów w całym napisie
Funkcja Z do wyszukiwania wzorców to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Kolejne narzędzie do dopasowywania
Funkcja Z jest przejrzystą alternatywą dla KMP podczas wyszukiwania wzorców. Wielu programistów uważa, że łatwiej o niej myśleć. ✨
Znaczenie z[i]
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.
Mały przykład
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.
Przedział Z
Śledzimy okno [l, r], czyli najbardziej wysunięte w prawo znalezione dopasowanie. Dzięki temu można ponownie wykorzystać wcześniejsze porównania.
l, r = 0, 0Wewnątrz przedziału
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.
if i < r:
z[i] = min(r - i, z[i - l])Wyjście poza przedział
Po takim wstępnym dopasowaniu należy nadal porównywać znaki jeden po drugim, dopóki pasują do prefiksu.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Przesuwanie przedziału w prawo
Jeśli dopasowanie sięga dalej w prawo, należy zaktualizować l i r, aby przyszłe indeksy mogły je ponownie wykorzystać.
if i + z[i] > r:
l, r = i, i + z[i]Gwarancja liniowego czasu
Przedział przesuwa się wyłącznie w prawo, więc całkowity nakład pracy wynosi O(n). Każdy znak wnosi ograniczoną ilość pracy.
Wyszukiwanie za pomocą funkcji Z
Należy połączyć pattern + sep + text i obliczyć funkcję Z. Każda wartość z równa długości wzorca oznacza dopasowanie.
combined = pattern + chr(0) + text
z = z_function(combined)Odczytywanie dopasowań
Należy przejrzeć tablicę Z; wszędzie tam, gdzie z[i] == len(pattern), dopasowanie zaczyna się w odpowiadającym miejscu tekstu.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z a KMP
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.
Szybkie sprawdzenie
Należy upewnić się, że znaczenie tablicy Z jest dobrze utrwalone.
Podsumowanie: funkcja Z wygrywa
Można już budować tablicę Z za pomocą przesuwanego przedziału, wyszukiwać w czasie liniowym i korzystać z przejrzystej alternatywy dla KMP. 🎯
Często zadawane pytania
Czy lekcja „Funkcja Z do wyszukiwania wzorców” jest bezpłatna?
Tak — pełny tekst „Funkcja Z do wyszukiwania wzorców” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Funkcja Z do wyszukiwania wzorców”?
Dopasowywanie prefiksów w całym napisie Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Funkcja Z do wyszukiwania wzorców”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Funkcja prefiksowa KMP
- Wielomianowe haszowanie napisów
- Funkcja Z do wyszukiwania wzorców
- Trie do wyszukiwania prefiksów