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.
31
Ćwiczenie 3
Napisz program, który zliczy w przekazanym tekście wszystkie wystąpienia wzorca. Wzorzec jest dowolnym ciągiem znaków o długości określonej przez zmienną dlugosc_wzorca, spełniającym następujące warunki:
jeżeli dlugosc_wzorca jest parzysta, wzorzec składa się z dowolnych małych liter i dowolnych dwóch wielkich liter pośrodku, np. werTTsug,
jeżeli dlugosc_wzorca jest nieparzysta, wzorzec składa się z dowolnych małych liter oraz jednej dowolnej wielkiej litery pośrodku, np. reWsd.
Do rozwiązania użyj implementacji algorytmu KMP, która została przedstawiona w sekcji „Przeczytaj” (przydatne może być również przeanalizowanie symulacji interaktywnej).
Przetestuj kod dla danych:
Linia 1. tekst znak równości cudzysłów 72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd cudzysłów.
Linia 2. dlugosc podkreślnik wzorca znak równości 8.
tekst = "72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd"
dlugosc_wzorca = 8
Specyfikacja:
Dane:
tekst – tekst dla poszukiwań wystąpień wzorca; łańcuch znaków
dlugosc_wzorca – długość poszukiwanego wzorca; dodatnia liczba całkowita
Wynik:
wystapienia – zliczone wystąpienia wzorca w tekście; nieujemna liczba całkowita
R1alrmBx43az1
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 zlicza wszystkie wystąpienia wzorca 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. wystapienia znak równości 0.
Linia 4. kratka tutaj dodaj kod.
Linia 6. return wystapienia.
Linia 9. tekst znak równości cudzysłów 72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd cudzysłów.
Linia 10. dlugosc podkreślnik wzorca znak równości 8.
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 zlicza wszystkie wystąpienia wzorca 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. tekst znak równości cudzysłów 72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd cudzysłów.
Linia 36. dlugosc podkreślnik wzorca znak równości 8.
Linia 38. wynik 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 wynik znak równości znak równości 3 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):
wystapienia = 0
# tutaj dodaj kod
return wystapienia
tekst = "72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd"
dlugosc_wzorca = 8
print(szukaj_algorytmem_KMP(tekst, dlugosc_wzorca))
@@@
language=python37
@@@
Program zlicza wszystkie wystąpienia wzorca 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)
#################################################################
tekst = "72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd"
dlugosc_wzorca = 8
wynik = szukaj_algorytmem_KMP(tekst, dlugosc_wzorca)
if wynik == 3:
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ł.
Podobnie, jak w programie prezentowanym w symulacji interaktywnej, zamiast tablicy częściowych dopasowań można przeanalizować strukturę wzorca i w przypadku znalezienia niedopasowania, podejmować odpowiednie działania na indeksie dop. Pozwala nam na to jego szczególna budowa. Analiza wzorca doprowadza do następujących wniosków w przypadku znalezienia niedopasowania:
jeżeli znak_S nie jest literą, to dop = początek wzorca, bo wzorzec nie zawiera takiego znaku,
jeżeli znak_S jest dużą literą i dop nie jest środkowym indeksem wzorca, to dop = początek wzorca, bo wzorzec nie zawiera takiego ułożenia dużych liter.
Dla nieparzystej długości wzorca:
jeżeli znak_S jest małą literą i dop jest środkowym indeksem wzorca, to dop = środkowy indeks - 1, ponieważ pomiędzy początkiem a środkiem wzorca znajduje się ciąg małych liter, który może być prefiksem dla dopasowania.
Dla parzystej długości wzorca:
jeżeli znak_S jest małą literą i dop jest lewym środkowym indeksem wzorca, to dop = środkowy indeks - 1, ponieważ pomiędzy początkiem a lewym środkiem wzorca znajduje się ciąg małych liter, który może być prefiksem dla dopasowania,
jeżeli znak_S jest małą literą i dop jest prawym środkowym indeksem wzorca, to dop = początek wzorca, ponieważ wzorzec nie zawiera takiego ustawienia dużych liter.
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 3. poczatek podkreślnik wzorca znak równości minus 1.
Linia 4. if dlugosc podkreślnik wzorca procent 2 znak równości znak równości 0 dwukropek.
Linia 5. srodek podkreślnik wzorca znak równości otwórz nawias kwadratowy otwórz nawias okrągły dlugosc podkreślnik wzorca prawy ukośnik prawy ukośnik 2 zamknij nawias okrągły minus 1 przecinek dlugosc podkreślnik wzorca prawy ukośnik prawy ukośnik 2 zamknij nawias kwadratowy kratka srodek podkreślnik wzorca jest listą jedno lub dwuelementową zależnie od parzystości.
Linia 6. kratka parametru dlugosc podkreślnik wzorca.
Linia 7. else dwukropek.
Linia 8. srodek podkreślnik wzorca znak równości otwórz nawias kwadratowy otwórz nawias okrągły dlugosc podkreślnik wzorca prawy ukośnik prawy ukośnik 2 zamknij nawias okrągły zamknij nawias kwadratowy.
Linia 10. wystapienia znak równości 0.
Linia 11. dop znak równości 0.
Linia 12. for indeks przecinek znak podkreślnik S in enumerate otwórz nawias okrągły tekst zamknij nawias okrągły dwukropek.
Linia 13. kratka jeżeli znaleziono niedopasowanie.
Linia 14. if dop zamknij nawias ostrokątny minus 1 and otwórz nawias okrągły not znak podkreślnik S kropka isalpha otwórz nawias okrągły zamknij nawias okrągły or otwórz nawias okrągły dop not in srodek podkreślnik wzorca and not znak podkreślnik S kropka islower otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły or otwórz nawias okrągły dop in srodek podkreślnik wzorca and not znak podkreślnik S kropka isupper otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 16. if dop znak równości znak równości srodek podkreślnik wzorca otwórz nawias kwadratowy 0 zamknij nawias kwadratowy dwukropek kratka w punktach nad kodem rozpisane są przypadki wartości znak podkreślnik S.
Linia 17. dop minus znak równości 1 kratka i odpowiednie wartości przecinek które są przypisywane dop.
Linia 18. else dwukropek.
Linia 19. dop znak równości poczatek podkreślnik wzorca.
Linia 20. dop plus znak równości 1.
Linia 21. if dop znak równości znak równości dlugosc podkreślnik wzorca dwukropek.
Linia 22. wystapienia plus znak równości 1 kratka jeżeli zostało znalezione dopasowanie przecinek to sufiks z małymi literami.
Linia 23. dop znak równości srodek podkreślnik wzorca otwórz nawias kwadratowy 0 zamknij nawias kwadratowy minus 1 kratka na końcu wzorca może być prefiksem dla kolejnego dopasowania przecinek.
Linia 24. kratka dlatego zmieniamy indeks dop na o 1 mniejszy niż indeks środka.
Linia 25. kratka otwórz nawias okrągły lub lewego środka w parzystym przypadku zamknij nawias okrągły.
Linia 26. return wystapienia.
Linia 29. tekst znak równości cudzysłów 72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd cudzysłów.
Linia 30. dlugosc podkreślnik wzorca znak równości 8.
Linia 31. 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.
def szukaj_algorytmem_KMP(tekst, dlugosc_wzorca):
poczatek_wzorca = -1
if dlugosc_wzorca % 2 == 0:
srodek_wzorca = [(dlugosc_wzorca // 2) - 1, dlugosc_wzorca // 2] # srodek_wzorca jest listą jedno lub dwuelementową zależnie od parzystości
# parametru dlugosc_wzorca
else:
srodek_wzorca = [(dlugosc_wzorca // 2)]
wystapienia = 0
dop = 0
for indeks, znak_S in enumerate(tekst):
# jeżeli znaleziono niedopasowanie
if dop > -1 and (not znak_S.isalpha() or (dop not in srodek_wzorca and not znak_S.islower()) or (dop in srodek_wzorca and not znak_S.isupper())):
if dop == srodek_wzorca[0]: # w punktach nad kodem rozpisane są przypadki wartości znak_S
dop -= 1 # i odpowiednie wartości, które są przypisywane dop
else:
dop = poczatek_wzorca
dop += 1
if dop == dlugosc_wzorca:
wystapienia += 1 # jeżeli zostało znalezione dopasowanie, to sufiks z małymi literami
dop = srodek_wzorca[0] - 1 # na końcu wzorca może być prefiksem dla kolejnego dopasowania,
# dlatego zmieniamy indeks dop na o 1 mniejszy niż indeks środka
# (lub lewego środka w parzystym przypadku)
return wystapienia
tekst = "72048agfds3423abcDDefg5902341asdfaweEEgafsdfawRRgdfsasd"
dlugosc_wzorca = 8
print(szukaj_algorytmem_KMP(tekst, dlugosc_wzorca))