W języku Python napisz program, który wyszuka w tekście pierwszy fragment o zadanej długości, złożony jedynie z cyfr. Użyj algorytmu KMP. Program powinien zwrócić indeks początku znalezionego wzorca w tekście. Działanie programu przetestuj dla przykładowych danych:
Linia 1. tekst znak równości cudzysłów ab3def45ab12345hijk cudzysłów.
Linia 2. dlugosc podkreślnik wzorca znak równości 5.
tekst = "ab3def45ab12345hijk"
dlugosc_wzorca = 5
Specyfikacja:
Dane:
tekst – przeszukiwany tekst; łańcuch znaków
dlugosc_wzorca – długość szukanego fragmentu w tekście; dodatnia liczba całkowita
Wynik:
wynikowy_indeks – indeks wskazujący w danym tekście na pierwszy znak znalezionego wzorca; jeżeli wzorzec nie został znaleziony, indeks jest równy -1; liczba całkowita
RkIKZAuApgISv1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Twoje zadanie: Program zwraca indeks wskazujący na początek znalezionego wzorca lub -1, jeżeli nie został on znaleziony w tekście.
Linia 1. def szukaj podkreślnik algorytmem podkreślnik KMP otwórz nawias okrągły tekst przecinek dlugosc podkreślnik wzorca zamknij nawias okrągły dwukropek.
Linia 2. wynikowy podkreślnik indeks znak równości minus 1.
Linia 4. kratka tutaj dodaj swój kod.
Linia 6. return wynikowy podkreślnik indeks.
Linia 8. tekst znak równości cudzysłów ab3def45ab12345hijk cudzysłów.
Linia 9. dlugosc podkreślnik wzorca znak równości 5.
Linia 11. print otwórz nawias okrągły szukaj podkreślnik algorytmem podkreślnik KMP otwórz nawias okrągły tekst przecinek dlugosc podkreślnik wzorca zamknij nawias okrągły zamknij nawias okrągły.
Linia 13. at at at.
Linia 14. language znak równości python37.
Linia 15. at at at.
Linia 16. Program zwraca indeks wskazujący na początek znalezionego wzorca lub minus 1 przecinek jeżeli nie został on znaleziony w tekście kropka.
Linia 17. at at at.
Linia 18. kratka ukryty kod przed kodem ucznia minus tu raczej nic nigdy.
Linia 19. at at at.
Linia 20. kratka po kodzie ucznia.
Linia 21. kratka przede wszystkim helper do zapisu wyników.
Linia 22. from sys import exit.
Linia 24. wyniki znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy kratka tablica zaliczonych wyników dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka zamknij nawias kwadratowy.
Linia 26. def podkreślnik zapisz podkreślnik wynik otwórz nawias okrągły lst zamknij nawias okrągły dwukropek.
Linia 27. w znak równości cudzysłów cudzysłów cudzysłów.
Linia 28. cudzysłów cudzysłów cudzysłów.
Linia 29. for q in lst dwukropek.
Linia 30. w plus znak równości str otwórz nawias okrągły q zamknij nawias okrągły plus chr otwórz nawias okrągły 10 zamknij nawias okrągły plus chr otwórz nawias okrągły 13 zamknij nawias okrągły.
Linia 31. with open otwórz nawias okrągły 3 przecinek apostrof w apostrof zamknij nawias okrągły as f dwukropek.
Linia 32. f kropka write otwórz nawias okrągły w zamknij nawias okrągły.
Linia 33. kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka kratka.
Linia 35. kratka pierwszy rodzaj testu.
Linia 36. tekst znak równości cudzysłów ab3def45ab12345hijk cudzysłów.
Linia 37. dlugosc podkreślnik wzorca znak równości 5.
Linia 38. pozycja znak równości szukaj podkreślnik algorytmem podkreślnik KMP otwórz nawias okrągły tekst przecinek dlugosc podkreślnik wzorca zamknij nawias okrągły.
Linia 39. if pozycja znak równości znak równości 10 dwukropek.
Linia 40. wyniki kropka append otwórz nawias okrągły 0 zamknij nawias okrągły.
Linia 42. kratka zapisuję wszystkie testy do pliku.
Linia 43. podkreślnik zapisz podkreślnik wynik otwórz nawias okrągły wyniki zamknij nawias okrągły.
Linia 45. at at at.
Linia 46. kratka wykrzyknik prawy ukośnik usr prawy ukośnik bin prawy ukośnik python3 kropka 7.
Linia 47. import sys.
Linia 48. kratka tutaj ewentualne sprawdzenie wykonania skryptu ucznia przecinek czy zwraca poprawne wyniki.
Linia 49. input znak równości sys kropka stdin kropka read otwórz nawias okrągły zamknij nawias okrągły kropka strip otwórz nawias okrągły zamknij nawias okrągły.
Linia 50. kratka ale raczej tego nie będę używał kropka.
def szukaj_algorytmem_KMP(tekst, dlugosc_wzorca):
wynikowy_indeks = -1
# tutaj dodaj swój kod
return wynikowy_indeks
tekst = "ab3def45ab12345hijk"
dlugosc_wzorca = 5
print(szukaj_algorytmem_KMP(tekst, dlugosc_wzorca))
@@@
language=python37
@@@
Program zwraca indeks wskazujący na początek znalezionego wzorca lub -1, jeżeli nie został on znaleziony w tekście.
@@@
# ukryty kod przed kodem ucznia - tu raczej nic nigdy
@@@
# po kodzie ucznia
# przede wszystkim helper do zapisu wyników
from sys import exit
wyniki = [] # tablica zaliczonych wyników: [0, 1, 2, ...]
def _zapisz_wynik(lst):
w = """
"""
for q in lst:
w += str(q) + chr(10) + chr(13)
with open(3,'w') as f:
f.write(w)
#################################################################
# pierwszy rodzaj testu
tekst = "ab3def45ab12345hijk"
dlugosc_wzorca = 5
pozycja = szukaj_algorytmem_KMP(tekst, dlugosc_wzorca)
if pozycja == 10:
wyniki.append(0)
# zapisuję wszystkie testy do pliku
_zapisz_wynik(wyniki)
@@@
#!/usr/bin/python3.7
import sys
# tutaj ewentualne sprawdzenie wykonania skryptu ucznia, czy zwraca poprawne wyniki
input = sys.stdin.read().strip()
# ale raczej tego nie będę używał.
1
Polecenie 1
Porównaj swoje rozwiązanie z prezentacją.
R1C9WKhbeWWyq1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.
1
Polecenie 2
Uruchom aplet realizujący wyszukiwanie wzorca w tekście. W aplecie znaki indeksowane są od 0 (czyli pierwszy znak ciągu ma indeks 0).
RyTj27iNx6A8L1
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.
Symulacja interaktywna przedstawia algorytm wyszukujący fragmentu tekstu w teście.
Na górze symulacji znajdują się dwa pola do wpisania tekstu, pierwsze to Przeszukiwany tekst, a drugi to Szukany wzorzec. Obok nich znajdują się przyciski Reset oraz kolejny krok.
Poniżej pól tekstowych i przycisków znajduje się napis Tablica T: -1 0 0, ponad liczbami znajduje się tekst szukanego wzorca. Poniżej tego napisu znajduje się Przeszukiwany tekst, a pod nim wzorzec szukany.
Przy każdym kolejnym kliknięciu przycisku kolejny krok, tekst szukany podświetla pierwszą literę obydwu tekstów oraz je porównuje.
Jeśli litery się nie zgadzają tekst szukany przesuwa się o literę w prawo i przy kolejnym kroku sprawdza ponownie. Jeśli litery się zgadzają, wtedy przy kolejnym kroku sprawdza kolejną literę tekstu szukanego.
Algorytm kontynuuje pracdo momentu odnalezienia całego tekstu bądź porażki.