Informatyka · Zakres podstawowy
Teksty — porównywanie i szukanie wzorca
Wyszukiwarka w notatce musi znaleźć słowo również wtedy, gdy występuje kilka razy. Zobaczmy, jak robi to najprostszy algorytm.
- Przewidź
- Sprawdź
- Wyjaśnij
Po tej lekcji: Porównasz napisy i znajdziesz wszystkie wystąpienia wzorca, także nakładające się.
Zakres podstawowy · materiał otwarty
Równe napisy czy kolejność?
== sprawdza identyczną zawartość, a < porównuje napisy leksykograficznie według wartości znaków Unicode. To nie zawsze polski porządek słownikowy. Wielkość liter i spacje mają znaczenie: Ala i ala różnią się. casefold() może pomóc w porównaniu bez wielkości liter, ale świadomie decyduj, co normalizujesz.
Porównaj dwie wiadomości
print("kot" == "kot")
print("kot" == "Kot")
print("kot" < "kotek")
print("ALA".casefold() == "ala".casefold())True False True True
Sprawdź w działaniu
Przesuń okienko po tekście
Dla ABABA szukaj ABA. Przesuwaj początek o jeden znak, nawet po znalezieniu zgodności.
Najpierw przewidź wynik, potem sprawdź i wyjaśnij różnicę.
Każda możliwa pozycja początku
tekst = "ABABA"
wzorzec = "ABA"
pozycje = []
for start in range(len(tekst) - len(wzorzec) + 1):
zgodny = True
for j in range(len(wzorzec)):
if tekst[start + j] != wzorzec[j]:
zgodny = False
break
if zgodny:
pozycje.append(start)
print(*pozycje)0 2
Dlaczego jest +1?
Ostatni dopuszczalny początek to n−m, ale range nie obejmuje prawej granicy. Gdy wzorzec jest dłuższy od tekstu, pętla nie rusza. W zadaniach wzorzec nie jest pusty; pusty wzorzec wymaga osobnej umowy. Najgorszy koszt wynosi O(n·m), np. gdy porównania długo pasują, a różnią się dopiero na końcu.
Ćwiczenie z pomocą · samodzielna praca
Nie zgub nakładania
Znajdź AA w AAAA. Narysuj każde okienko i podaj początki numerowane od zera.
0 1 2
? Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź
Okienko ma dwa znaki.
Krok 2 — pokaż podpowiedź
Możesz zacząć w pozycjach 0,1,2.
Krok 3 — pokaż podpowiedź
Po dopasowaniu przesuwasz się o jeden, nie o dwa.
Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.
Podsumowanie
Zapamiętaj
- Porównanie jest zależne od znaków i ich wielkości.
- Naiwne szukanie bada każdy możliwy początek.
- Wystąpienia mogą się nakładać.
Po zalogowaniu zobaczysz dodatkowe lekcje i materiały oznaczone jako rozszerzenie. Podstawowe quizy i zadania pozostają dostępne w biurku.
Dalej na swoim koncie
Rozgrzewki, quiz i zadania są w biurku ucznia.
Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.
Zaloguj się →