Czego się nauczysz
Nauczysz się zamieniać napis w liczbę, czyli hasz, i szukać wzorca, porównując liczby zamiast liter. Hasz kolejnego fragmentu tekstu policzysz z poprzedniego w jednym kroku. Tak działa algorytm Rabina-Karpa.
Po co ci to na maturze
Na maturze zwykle wystarcza zwykłe szukanie wzorca, ale hasz to pomysł, który pozwala porównać dwa długie napisy jedną liczbą. Przydaje się, gdy porównań jest bardzo dużo, np. przy szukaniu powtarzających się fragmentów długiego tekstu.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Hasz: odcisk palca napisuFunkcja haszująca zamienia napis w liczbę. Ten sam napis daje zawsze tę samą liczbę.
- 1.2Rabin-Karp: okno przesuwane o znakHasz następnego okna to poprzedni hasz minus znak, który wyszedł, plus znak, który wszedł.
- 1.3Przesuwanie haszu wielomianowegoNajstarsza pozycja ma największą wagę: odejmij ją, pomnóż przez B i dołóż nowy znak.
- 1.4Okna z anagramem wzorcaKolizje sumy kodów przy anagramach można wykorzystać: hasz odsiewa okna, a posortowane litery rozstrzygają.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.