Ten artykuł jest przeznaczony dla uczniów klasy 3 liceum (poziom podstawowy). Pokażemy, jak w języku Python zaimplementować naiwny algorytm wyszukiwania wzorca w tekście, tak jak na skanach z podręcznika, ale tylko w wersji pythonowej.
1. Co robi nasz program?
Mamy dwa napisy (stringi):
- tekst – dłuższy napis, w którym szukamy, np.
"matematyka" - wzorzec – krótszy napis, którego szukamy, np.
"mat"
Chcemy:
- sprawdzić, czy wzorzec występuje w tekście,
- jeśli tak – znaleźć pozycję (indeks) pierwszego znaku wzorca,
- ewentualnie wypisać wszystkie wystąpienia wzorca.
Indeksy znaków w Pythonie zaczynają się od 0:
tekst = "matematyka"
# m(0), a(1), t(2), e(3), m(4), a(5), t(6), y(7), k(8), a(9)
2. Krótkie przypomnienie z Pythona
- String (łańcuch znaków):
tekst = "matematyka" wzorzec = "mat" - Długość napisu –
len():dl1 = len(tekst) # długość tekstu dl2 = len(wzorzec) # długość wzorca - Pętla
forzrange():for i in range(5): print(i) # wypisze 0, 1, 2, 3, 4 - Funkcja z argumentami i wynikiem:
def dodaj(a, b): return a + b x = dodaj(2, 3) # x = 5
3. Funkcja znajdz_wzorzec – serce algorytmu
W podręczniku wprowadzono funkcję znajdz_wzorzec(tekst, wzorzec, pozycja_startowa). Szukamy wzorca w tekście, zaczynając od podanej pozycji. Funkcja zwraca:
- indeks pierwszego znaku wzorca – jeśli został znaleziony,
-1, jeśli wzorzec się nie pojawia.
def znajdz_wzorzec(tekst, wzorzec, pozycja_startowa):
dl1 = len(tekst) # długość tekstu
dl2 = len(wzorzec) # długość wzorca
# przechodzimy po możliwych początkach wzorca
for i in range(pozycja_startowa, dl1 - dl2 + 1):
j = 0
# sprawdzamy kolejne znaki wzorca
while j < dl2 and tekst[i + j] == wzorzec[j]:
j += 1
# jeśli sprawdziliśmy wszystkie znaki wzorca i były zgodne
if j == dl2:
return i # znaleziono wzorzec zaczynający się na pozycji i
# nie znaleziono wzorca
return -1
Uwaga: warunek dl1 - dl2 + 1 pilnuje, abyśmy nie wyszli poza tekst.
4. Jak działa funkcja – tabela krok po kroku
Przykład z podręcznika:
tekst = "matematyka"
wzorzec = "mat"
pozycja_startowa = 0
Długości: dl1 = 10, dl2 = 3. Pętla for wykona się dla i = 0, 1, ..., 7, ale wzorzec zostanie znaleziony już dla i = 0.
| krok | i | j | tekst[i + j] | wzorzec[j] | co się dzieje? |
|---|---|---|---|---|---|
| 1 | 0 | 0 | m | m | warunek w while spełniony, j zwiększa się na 1 |
| 2 | 0 | 1 | a | a | dalej pasuje, j = 2 |
| 3 | 0 | 2 | t | t | dalej pasuje, j = 3 |
| 4 | 0 | 3 | – | – | warunek j < dl2 jest fałszywy (3 < 3 nie), wyjście z while |
| 5 | 0 | 3 | – | – | j = dl2, więc funkcja zwraca i = 0 (wzorzec znaleziony) |
Funkcja kończy działanie od razu po znalezieniu pierwszego dopasowania.
5. Program 1 – szukanie pierwszego wystąpienia wzorca
Teraz użyjemy funkcji w prostym programie głównym.
def znajdz_wzorzec(tekst, wzorzec, pozycja_startowa):
dl1 = len(tekst)
dl2 = len(wzorzec)
for i in range(pozycja_startowa, dl1 - dl2 + 1):
j = 0
while j < dl2 and tekst[i + j] == wzorzec[j]:
j += 1
if j == dl2:
return i
return -1
# --- program główny ---
tekst = input("Podaj tekst do przeszukania: ")
wzorzec = input("Podaj tekst do wyszukania (wzorzec): ")
pozycja = znajdz_wzorzec(tekst, wzorzec, 0)
if pozycja == -1:
print("Wzorzec nie został znaleziony.")
else:
print("Wzorzec znaleziono na pozycji:", pozycja)
Wyjaśnienie
- Wczytujemy
tekstiwzorzecz klawiatury. - Wywołujemy
znajdz_wzorzec(tekst, wzorzec, 0)– szukamy od początku. - Jeśli wynik to
-1– wypisujemy komunikat, że nie znaleziono. - Jeśli wynik to liczba ≥ 0 – wypisujemy indeks znalezienia.
6. Program 2 – wszystkie wystąpienia wzorca
Funkcja znajdz_wzorzec znajduje tylko pierwsze dopasowanie od pozycji startowej. Aby znaleźć wszystkie wystąpienia, powtarzamy wyszukiwanie w pętli, za każdym razem startując od miejsca tuż za poprzednim znalezieniem.
def znajdz_wzorzec(tekst, wzorzec, pozycja_startowa):
dl1 = len(tekst)
dl2 = len(wzorzec)
for i in range(pozycja_startowa, dl1 - dl2 + 1):
j = 0
while j < dl2 and tekst[i + j] == wzorzec[j]:
j += 1
if j == dl2:
return i
return -1
# --- program główny ---
tekst = input("Podaj tekst do przeszukania: ")
wzorzec = input("Podaj tekst do wyszukania (wzorzec): ")
pozycja_startowa = 0
znalezione = 0
while True:
pozycja = znajdz_wzorzec(tekst, wzorzec, pozycja_startowa)
if pozycja == -1:
break # nie ma więcej wystąpień
print("Znaleziono na pozycji:", pozycja)
znalezione += 1
pozycja_startowa = pozycja + 1 # szukamy dalej, za tym wystąpieniem
if znalezione == 0:
print("Wzorzec nie występuje w tekście.")
Wyjaśnienie
pozycja_startowa– od tego miejsca w tekście zaczynamy szukać.- W pętli:
- wzywamy funkcję
znajdz_wzorzec, - jeśli zwróci
-1– wychodzimy z pętli (break), - w przeciwnym razie wypisujemy znalezioną pozycję.
- wzywamy funkcję
- Po każdym znalezieniu ustawiamy
pozycja_startowa = pozycja + 1, żeby nie znaleźć tego samego miejsca jeszcze raz.
7. Zadania z wyjaśnieniami (na bazie tych z podręcznika)
Zadanie 1. Imię żeńskie czy męskie?
Napisz program, który sprawdza, czy podane przez użytkownika polskie imię jest imieniem męskim czy żeńskim. Przyjmujemy uproszczenie: imiona żeńskie kończą się na literę "a".
Rozwiązanie (Python)
imie = input("Podaj imię: ")
if len(imie) == 0:
print("Nie podano imienia.")
else:
ostatnia_litera = imie[-1] # ostatni znak
if ostatnia_litera == "a":
print("To imię żeńskie.")
else:
print("To imię męskie (wg naszego uproszczenia).")
Wyjaśnienie:
imie[-1]– ostatni znak napisu.- Jeśli to
"a", wypisujemy, że imię jest żeńskie. - W przeciwnym razie – męskie (według uproszczonej zasady).
Zadanie 2. Liczenie liter a, b lub c
Napisz program, który w wprowadzonym tekście liczy: liczbę liter "a", albo "b", albo "c" – w zależności od znaku opcji podanego przez użytkownika ('a', 'b' lub 'c').
Rozwiązanie (Python)
tekst = input("Podaj tekst: ")
opcja = input("Którą literę liczyć (a/b/c)? ")
if opcja not in ["a", "b", "c"]:
print("Nieprawidłowa opcja.")
else:
licznik = 0
for znak in tekst:
if znak == opcja:
licznik += 1
print(f"Liczba liter '{opcja}' w tekście wynosi:", licznik)
Wyjaśnienie:
- Użytkownik wybiera literę
'a','b'lub'c'. - Pętla
for znak in tekstprzechodzi po wszystkich znakach. - Jeśli znak jest równy wybranej literze, zwiększamy licznik.
Zadanie 3. Prosty wybór komunikatu
Wczytaj jeden znak. Jeśli to 'i', wypisz „twoje imię”, jeśli 'n' – „twoje nazwisko”, a w innym przypadku wypisz „błędny znak”.
Rozwiązanie (Python)
znak = input("Podaj znak (i/n): ")
if znak == "i":
print("twoje imię")
elif znak == "n":
print("twoje nazwisko")
else:
print("błędny znak")
Wyjaśnienie: używamy instrukcji if / elif / else, żeby wybrać odpowiedni komunikat.
Zadanie 4. Ile wyrazów w zdaniu?
Napisz program, który sprawdzi, z ilu wyrazów składa się wprowadzone zdanie. Zakładamy, że wyrazy są oddzielone spacjami, a zdanie kończy się kropką.
Rozwiązanie (Python)
zdanie = input("Podaj zdanie zakończone kropką: ")
# usuwamy kropkę z końca (jeśli jest)
if zdanie.endswith("."):
zdanie = zdanie[:-1]
wyrazy = zdanie.split() # dzieli po spacjach
liczba_wyrazow = len(wyrazy)
print("Liczba wyrazów w zdaniu:", liczba_wyrazow)
Wyjaśnienie:
zdanie.endswith(".")– sprawdza, czy zdanie kończy się kropką.zdanie[:-1]– usuwa ostatni znak (kropkę).split()dzieli tekst na listę wyrazów według spacji.len(wyrazy)– liczba elementów listy, czyli liczba wyrazów.
Zadanie 5. Palindrom
Napisz program, który sprawdza, czy dany ciąg znaków jest palindromem – tzn. czy czyta się tak samo od lewej i od prawej strony, np. "kajak", "potop".
Rozwiązanie (Python)
napis = input("Podaj napis: ")
# porównujemy napis z jego wersją odwróconą
odwrocony = napis[::-1]
if napis == odwrocony:
print("To jest palindrom.")
else:
print("To nie jest palindrom.")
Wyjaśnienie:
napis[::-1]– zapis odczytujący napis od końca.- Jeśli napis jest taki sam jak jego odwrócona wersja – mamy palindrom.
8. Dwa bardzo proste zadania dodatkowe
Zadanie dodatkowe 1. Szukanie litery w napisie
Napisz funkcję, która zwraca indeks pierwszego wystąpienia litery "x" w podanym tekście (użyj dokładnie tego samego pomysłu, co w algorytmie naiwnym).
Rozwiązanie
def znajdz_x(tekst):
for i in range(len(tekst)):
if tekst[i] == "x":
return i
return -1
print(znajdz_x("abrakadabra")) # -1
print(znajdz_x("xyz")) # 0
Wyjaśnienie: to specjalny przypadek algorytmu wyszukiwania, gdzie wzorcem jest tylko jeden znak "x".
Zadanie dodatkowe 2. Proste wyszukiwanie słowa
Napisz funkcję, która sprawdzi, czy w tekście występuje słowo "tak". Zwróć True, jeśli występuje, inaczej False.
Rozwiązanie
def czy_jest_tak(tekst):
wzorzec = "tak"
dl1 = len(tekst)
dl2 = len(wzorzec)
for i in range(0, dl1 - dl2 + 1):
fragment = tekst[i:i+dl2]
if fragment == wzorzec:
return True
return False
print(czy_jest_tak("czy tak czy nie")) # True
print(czy_jest_tak("nie wiem")) # False
Wyjaśnienie: to dokładnie ten sam naiwny algorytm, tylko wzorzec mamy na stałe ustawiony na "tak".
9. Podsumowanie – co warto zapamiętać
- Aby zaprogramować algorytm wyszukiwania wzorca w tekście, definiujemy funkcję zwracającą indeks pierwszego znaku wzorca lub
-1, jeśli wzorzec nie występuje. - Funkcja
znajdz_wzorzeckorzysta z:- pętli po możliwych pozycjach w tekście (
for i in range(...)), - pętli sprawdzającej kolejne znaki wzorca (
while), - porównywania znaków
tekst[i + j]iwzorzec[j].
- pętli po możliwych pozycjach w tekście (
- Aby znaleźć wszystkie wystąpienia wzorca, wywołujemy funkcję wiele razy w pętli, za każdym razem startując wyszukiwanie od pozycji tuż za poprzednim znalezieniem.
- Ćwiczenia z końca tematu (liczenie liter, sprawdzanie imion, palindromy) pomagają oswoić się z operacjami na stringach w Pythonie.
