Funkcja prefiksowa KMP
Znajdowanie wzorca w O(n + m)
Funkcja prefiksowa KMP to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 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.
Problem dopasowywania wzorca
Chcesz znaleźć miejsca, w których mały wzorzec pojawia się w dużym tekście. Naiwne sprawdzanie jest powolne, dlatego w zadaniach konkursowych warto użyć sprytniejszego skanowania. 🔍
Dlaczego naiwne wyszukiwanie jest kosztowne
Porównywanie wzorca w każdej pozycji może kosztować O(n*m) czasu. Przy dużych danych wejściowych łatwo po cichu przekroczyć limit czasu.
Poznaj funkcję prefiksową
Funkcja prefiksowa mierzy w każdej pozycji długość najdłuższego właściwego prefiksu, który jest jednocześnie sufiksem. To serce algorytmu KMP.
Właściwy prefiks i sufiks
Właściwy prefiks lub sufiks nie obejmuje całego napisu. Dla ababa najdłuższa zgodna para ma długość 3: aba.
Co przechowuje pi[i]
Wartości przechowujemy w tablicy o nazwie pi. W tym przypadku pi[i] to długość najdłuższej pary prefiks–sufiks dla fragmentu kończącego się na indeksie i.
Budowanie pi w jednym przejściu
Budujesz pi od lewej do prawej, wykorzystując wcześniejsze wartości zamiast ponownie sprawdzać wszystko od początku. To ponowne wykorzystanie jest całą sztuczką.
def prefix_function(s):
pi = [0] * len(s)
return piPętla wycofania
Gdy znaki się nie zgadzają, wycofujesz się do pi[k-1] zamiast zerować wartość. Dzięki temu nie wykonujesz tej samej pracy ponownie.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Wydłużanie dopasowania
Jeśli bieżące znaki się zgadzają, zwiększ długość o jeden i zapisz wynik. Niezgodność przy wartości zero po prostu pozostawia zero.
if s[i] == s[k]:
k += 1
pi[i] = kWyszukiwanie za pomocą sztuczki
Aby wyszukać wzorzec w tekście, połącz je jako pattern + sep + text. Każda wartość pi równa długości wzorca oznacza pełne dopasowanie.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Dlaczego separator ma znaczenie
Separator to symbol, który nie występuje w żadnym z obu napisów. Uniemożliwia on przenikanie dopasowań przez miejsce połączenia i powstawanie fałszywych trafień.
Zysk wynikający z liniowego czasu
Budowanie i wyszukiwanie działają w czasie O(n + m). Każdy znak jest przetwarzany raz, więc KMP skaluje się do ogromnych danych wejściowych w zadaniach konkursowych.
Szybkie sprawdzenie
Sprawdź, czy rozumiesz, co zapisuje funkcja prefiksowa.
Podsumowanie: KMP w skrócie
Poznałeś(-aś) funkcję prefiksową: zbuduj pi raz, przy niezgodnościach wycofuj się i wyszukuj w czasie liniowym. W skrócie tak działa KMP. 🎯
Często zadawane pytania
Czy lekcja „Funkcja prefiksowa KMP” jest bezpłatna?
Tak — pełny tekst „Funkcja prefiksowa KMP” 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 prefiksowa KMP”?
Znajdowanie wzorca w O(n + m) Ć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 1 z 4.
Ile czasu zajmuje lekcja „Funkcja prefiksowa KMP”?
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