Wielomianowe haszowanie napisów
Porównywanie podnapisów w stałym czasie
Wielomianowe haszowanie napisów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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.
Szybkie porównywanie podnapisów
Często trzeba sprawdzić, czy dwa podnapisy są równe. Sprawdzanie znak po znaku jest powolne, więc zamieniamy każdy napis na liczbę. 🔢
Idea haszowania
Hash odwzorowuje napis na pojedynczą liczbę całkowitą. Jeśli dwa napisy się różnią, ich hashe niemal zawsze również będą różne.
Traktuj napisy jak wielomiany
Odczytujemy każdy znak jako cyfrę w systemie o podstawie p. To wielomianowe ujęcie zamienia napis w jedną dużą sumę ważoną.
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pWybierz podstawę i moduł
Wybierz pierwszą podstawę, na przykład 31, oraz duży pierwszy moduł. Moduł utrzymuje małe liczby i zapobiega przepełnieniu.
BASE = 31
MOD = 10**9 + 9Obliczanie pojedynczego hasha
Przejdź po napisie i dodawaj kolejne znaki zgodnie ze schematem Hornera, wykonując operację modulo na każdym kroku.
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODHashe prefiksowe
Przechowuj hash prefiksowy dla każdej pozycji. Wtedy hash dowolnego podnapisu uzyskasz przez szybkie odejmowanie.
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODPotęgi podstawy
Wcześniej oblicz również potęgi podstawy. Wyrównują one oba prefiksy podczas odejmowania.
pw[i] = (pw[i - 1] * BASE) % MODHash podnapisu w O(1)
Hash s[l..r] to odejmowanie dwóch hashy prefiksowych przeskalowanych przez potęgę. Każde zapytanie trwa stały czas.
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODUwaga na kolizje
Dwa różne napisy mogą mieć ten sam hash — jest to kolizja. Zdarza się rzadko, ale w zadaniach konkursowych czasem konstruuje się dane wejściowe, które ją wywołują.
Podwójne haszowanie dla bezpieczeństwa
Należy użyć dwóch niezależnych modułów i porównać oba hashe. Jednoczesna kolizja dla obu jest praktycznie niemożliwa.
Gdzie haszowanie sprawdza się najlepiej
Haszowanie umożliwia porównywanie podnapisów, znajdowanie powtórzeń i wyszukiwanie wzorców. To wszechstronne narzędzie do wielu zadań.
Szybkie sprawdzenie
Należy wybrać właściwe narzędzie do bezpiecznego porównywania wielu podnapisów.
Podsumowanie: haszowanie wygrywa
Można już zamieniać napisy na hashe wielomianowe, odpytywać o dowolny podnapis w O(1) i zabezpieczać się przed kolizjami. 🚀
Często zadawane pytania
Czy lekcja „Wielomianowe haszowanie napisów” jest bezpłatna?
Tak — pełny tekst „Wielomianowe haszowanie napisó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 „Wielomianowe haszowanie napisów”?
Porównywanie podnapisów w stałym czasie Ć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 2 z 4.
Ile czasu zajmuje lekcja „Wielomianowe haszowanie napisó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