Aplet
Napisz w języku Java program wykorzystujący algorytm KMP. Użyj go do wyszukania wzorca wzorzec w tekście tekst. Przetestuj program dla wzorca AABAA oraz tekstu BBAABAABAA.
Specyfikacja problemu:
Dane:
wzorzec – ciąg znaków
tekst – ciąg znaków
Wynik:
Program wyświetla komunikat mówiący o tym, od którego indeksu został znaleziony wzorzec w tekście.
Porównaj swoje rozwiązanie z filmem przedstawiającym implementację algorytmu KMP, który został wykorzystany do wyszukania wzorca w tekście.
Film dostępny pod adresem /preview/resource/RxrNbx9xEaN09
Film nawiązujący do treści materiału: Algorytmy tekstowe - wyszukiwanie wzorca w tekście.
Kod programu zaprezentowanego w filmie:
Uruchom aplet prezentujący działanie algorytmu Knutha‑Morrisa‑Pratta. Sprawdź kolejne kroki wyszukiwania wzorca w tekście. Przetestuj, jak algorytm zachowa się w przypadku braku wzorca w tekście.
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/Dfw7072cg
Grafika interaktywna przedstawia sposób działania algorytmu wyszukującego ten sam ciąg znaków złożonych z symboli A, G, C oraz T.
Grafika posiada przyciski cofnij oraz dalej. Nad nimi znajdują się dwa pola dla tekstu oraz wzorca.
Animacja przedstawia w tabelce tekst, nad którym znajdują się numery indeksów od 0 do 23.
Pod tekstem w tabeli znajduje się kolejna tabela z 2 rzędami,
w pierwszym znajduje się wzorzec,
w drugim znajduje się wyrazy T [ i ].
W trakcie animacji tabela dolna przesuwa się pod górną, dzieje się tak w trakcie oznaczania kolorem zielonym takie same litery, bądź czerwonym błędne.
Tabelka będzie się przesuwała dopóki nie odnajdzie wszystkich liter w odpowiedniej kolejności względem wzorca.
Lekarzom udało się wyodrębnić łańcuch DNA odpowiedzialny za pewną mutację. W ramach badań zebrano grupę chętnych pacjentów, którzy poddali się badaniom genetycznym. Na podstawie fragmentów sekwencji DNA wskaż, czy wśród pacjentów są osoby ze wskazaną mutacją genową.
Dane:
GAGTTGTGCCAACCCTCGTCCTCACCGAAGCTTGCTGCCAATGATTAGGA – pacjent nr 1
TCATTGCCTTGCGACAGACCTCCCACTCACACTCGCTCGCATTGAGCTAC – pacjent nr 2
TCGATGGGCCATCAGCTTGACCCGCTCTGTAGGGTCGCGATTACGTGAGT – pacjent nr 3
CGCCTTCT – mutacja