Czego się nauczysz
Nauczysz się szukać wzorca w tekście tak, żeby po niezgodności nie cofać się w tekście, tylko skorzystać z tego, co już wiadomo o wzorcu.
Po co ci to na maturze
Na maturze do szukania wzorca wystarcza metoda naiwna, a KMP wykracza poza podstawę programową. Warto go znać, jeśli celujesz w 100% i chcesz wiedzieć, jak szukać szybko w bardzo długim tekście.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Nie cofaj się w tekściePasujący kawałek wzorca kończy się czasem jego własnym początkiem. Wtedy porównania nie trzeba zaczynać od nowa.
- 1.2Tablica prefiksowaP[i] to długość najdłuższego prefikso-sufiksu początku wzorca kończącego się na i.
- 1.3Szukanie z tablicąTa sama pętla co przy tablicy, tylko po tekście. Po trafieniu j wraca do P[j - 1].
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.