BLOK 06 · 2 godz. Tekst Kryptografia Wzorce

Algorytmy tekstowe: szyfr Cezara, palindromy, anagramy, wyszukiwanie wzorca

Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 06/30

1. Szyfr Cezara

Jeden z najstarszych szyfrów podstawieniowych — każdą literę przesuwamy o stałą liczbę pozycji w alfabecie (klucz). Deszyfrowanie to przesunięcie w przeciwną stronę.

def szyfruj_cezar(tekst, klucz): wynik = "" for znak in tekst: if znak.isalpha(): baza = ord('A') if znak.isupper() else ord('a') wynik += chr((ord(znak) - baza + klucz) % 26 + baza) else: wynik += znak return wynik # szyfruj_cezar("ATAK O SWICIE", 3) -> "DWDN R VZLFLWH" # deszyfrowanie = szyfruj_cezar(tekst, -klucz)

Dlaczego to słaby szyfr?

Ma tylko 25 możliwych kluczy — można go złamać metodą brute-force w ułamek sekundy, sprawdzając wszystkie przesunięcia i wybierając to, które daje sensowny tekst.

2. Palindromy i anagramy

def czy_palindrom(s): s = s.lower().replace(" ", "") return s == s[::-1] def czy_anagram(a, b): return sorted(a.lower()) == sorted(b.lower()) # czy_palindrom("kajak") -> True # czy_anagram("kot", "tok") -> True

Sprawdzanie anagramu przez sortowanie liter ma złożoność \(O(n \log n)\). Jeśli chcemy przyspieszyć działanie do czasu liniowego \(O(n)\), możemy zliczyć wystąpienia liter za pomocą słownika (lub tablicy zliczeń):

def czy_anagram_optymalnie(a, b): # Jeśli słowa mają różne długości, nie mogą być anagramami if len(a) != len(b): return False liczniki = {} # Zliczamy litery w pierwszym słowie i odejmujemy w drugim for litera in a.lower(): liczniki[litera] = liczniki.get(litera, 0) + 1 for litera in b.lower(): if litera not in liczniki or liczniki[litera] == 0: return False liczniki[litera] -= 1 return True

3. Naiwne wyszukiwanie wzorca w tekście

Zadanie: znaleźć wszystkie wystąpienia wzorca (o długości m) w tekście (o długości n). Metoda naiwna: dla każdej możliwej pozycji początkowej w tekście porównujemy znak po znaku ze wzorcem.

def szukaj_wzorca(tekst, wzorzec): n, m = len(tekst), len(wzorzec) wystapienia = [] for i in range(n - m + 1): if tekst[i:i+m] == wzorzec: wystapienia.append(i) return wystapienia

Złożoność tej metody w najgorszym przypadku to O(n × m) — dla każdej z n-m+1 pozycji możemy wykonać do m porównań.

4. Ćwiczenia praktyczne

Ćwiczenie 1 — złam szyfr Cezara

Napisz funkcję, która automatycznie łamie szyfr Cezara metodą brute-force: sprawdza wszystkie 25 możliwych kluczy i wypisuje wszystkie odszyfrowane wersje, aby człowiek mógł wybrać tę sensowną.

def lamacz_cezara(tekst_zaszyfrowany): for klucz in range(26): print(klucz, ":", szyfruj_cezar(tekst_zaszyfrowany, -klucz))

Ćwiczenie 2 — najdłuższy palindrom w zdaniu

Mając dane zdanie, znajdź najdłuższy pojedynczy wyraz będący palindromem (pomijając wielkość liter). Wykorzystaj funkcję czy_palindrom i metodę .split().

def czy_palindrom(s): s = s.lower().replace(" ", "") return s == s[::-1] def znajdz_najdluzszy_palindrom(zdanie): # 1. Czyszczenie tekstu z podstawowych znaków interpunkcyjnych znaki_interpunkcyjne = ",.?!:;" for znak in znaki_interpunkcyjne: zdanie = zdanie.replace(znak, "") # 2. Podział zdania na listę pojedynczych słów wyrazy = zdanie.split() # 3. Zmienna do przechowywania najlepszego wyniku najdluzszy = "" # 4. Przeglądanie każdego słowa po kolei for wyraz in wyrazy: # Sprawdzenie dwóch warunków jednocześnie if czy_palindrom(wyraz) and len(wyraz) > len(najdluzszy): najdluzszy = wyraz return najdluzszy # Przykład testowy: tekst_testowy = "Znasz ten owoc? To czerwony kajak, a obok stoi potok." print("Wynik:", znajdz_najdluzszy_palindrom(tekst_testowy)) # Program wypisze: kajak

🔍 Dokładne wyjaśnienie działania kodu:

  • czy_palindrom(s): s.lower() – zamienia wszystkie litery na małe, aby wielkość liter nie wpływała na wynik (np. "Kajak" zmieni się na "kajak"). s[::-1] to tzw. slicing w Pythonie (czytanie od tyłu z krokiem -1).
  • Usuwanie interpunkcji (pętla po znaki_interpunkcyjne): Zapobiega sytuacji, w której wyraz z kropką lub przecinkiem (np. "kajak.") nie zostałby rozpoznany jako palindrom.
  • zdanie.split(): Dzieli ciąg znaków wszędzie tam, gdzie występuje spacja, tworząc listę słów ['Znasz', 'ten', 'owoc', ...].
  • Wyszukiwanie lidera (pętla for i warunek and): Zaczynamy z pustym napisem najdluzszy = "". Dla każdego słowa sprawdzamy czy jest palindromem oraz czy jego długość jest ściśle większa od dotychczasowego maksimum (len(wyraz) > len(najdluzszy)). Dzięki temu słowo "potok" (5 liter) nie nadpisze wcześniejszego "kajak" (5 liter), zachowując pierwsze najdłuższe wystąpienie.

💥 Wskazówka dla maturzysty: Pułapki w algorytmach tekstowych

W przypadku wyszukiwania wzorca (Punkt 3) uczniowie często zapominają, dlaczego pętla wykonuje się do indeksu n - m + 1. Wyjaśnienie: Przeszukiwanie tekstu kończymy w momencie, gdy do końca tekstu zostało mniej znaków, niż wynosi długość wzorca – dalsze sprawdzanie nie ma sensu matematycznego.

Sprawdź wiedzę

1. Ile możliwych kluczy ma klasyczny szyfr Cezara (alfabet łaciński)?

2. Jaka jest złożoność czasowa naiwnego wyszukiwania wzorca w tekście?

3. Która metoda sprawdzenia, czy dwa słowa są anagramami, ma złożoność O(n log n)?

Podsumowanie bloku

← Blok 05: Bisekcja i Horner Blok 07: Grafy →