Fotografia przedstawia okulary i lupę powiększającą leżące na otwartej książce.
I_P_W14_M16 Algorytm Knutha‑Morrisa‑Pratta
Źródło: Wallace Chuck, domena publiczna.
Jeśli w czytanym e‑booku chcesz znaleźć wybrane słowo, korzystasz z wbudowanej wyszukiwarki. Nie porównujesz wszystkich ciągów znaków po kolei, nie szukasz losowo. Gdyby jednak ktoś chciał sprawdzać ciągi znaków, pomocny będzie algorytm Knutha‑Morrisa‑Pratta. Wyszukuje on tzw. wzorce w tekście.
Ćwiczenie na rozgrzewkę:
Ćwiczenie 1
Twoje cele
Przeanalizujesz proces wyszukiwania wzorców w tekście, w szczególności zagadnienie wykorzystania metody Knutha‑Morrisa‑Pratta.
Przeprowadzisz krok po kroku proces, który doprowadzi cię do odszukania wzorca w tekście.
Porównasz algorytm KMP z metodami naiwnymi.
Zaimplementujesz algorytm tworzenia tablicy częściowych dopasowań w języku Java.
Zaimplementujesz algorytm wyszukiwania wzorców metodą Knutha‑Morrisa‑Pratta w języku Java.