Przetwarzanie napisów, szyfrowanie, anagramy i wyszukiwanie wzorców. Kluczowe techniki pracy z tekstem, hasełami i ciągami DNA.
Wstęp: Świat ukryty w napisach
Praca z tekstem na maturze to nie tylko wyświetlanie komunikatów. To zaawansowane operacje na ciągach DNA, łamanie szyfrów i analiza struktur haseł. W Pythonie napisy (stringi) są obiektami niemodyfikowalnymi (immutable), co oznacza, że każda zmiana tworzy tak naprawdę nowy napis. Zrozumienie tablicy ASCII oraz metod manipulacji tekstem to klucz do zdobycia kompletu punktów w zadaniach ze słowami.
🔤 Spis treści: Algorytmy Tekstowe
1
Podstawowe operacje: Podciągi i Łączenie
W Pythonie tekst (typ str) to w rzeczywistości ciąg znaków, który pod wieloma względami zachowuje się jak lista. Z jedną ważną różnicą – jest niemodyfikowalny (nie możesz zmienić jednej litery w środku słowa, musisz stworzyć nowe słowo). Zobaczmy, jakimi narzędziami dysponujesz na maturze.
# Konkatenacja (Łączenie)
poczatek = "Ala ma"
koniec = "kota"
zdanie = poczatek + " " + koniec
# Powielanie (Mnożenie)
kreska = "-" * 20
print(kreska) # Wypisze 20 myślników!
in.dna = "TGACTAGC"
# Błyskawiczne szukanie wzorca
if "ACT" in dna:
print("Znaleziono kodon ACT!")
# Wycinanie podciągu (Slicing)
fragment = dna[2:5] # "ACT"
Znasz już sposób sprawdzania palindromów jedną linijką: s == s[::-1]. Pamiętaj jednak o krytycznej pułapce! Dla komputera "K" (ASCII 75) oraz "k" (ASCII 107) to dwa zupełnie różne znaki. Słowo "Kajak" nie przejdzie testu na palindrom, jeśli go wcześniej nie ujednolicisz.
slowo = "Kajak"
# 1. Zmieniamy wszystko na małe litery (.lower())
# (Możesz też użyć .upper() dla wielkich)
czyste = slowo.lower()
# 2. Bezpieczny test
if czyste == czyste[::-1]:
print("Prawidłowy palindrom!")
2
Anagramy: Porównywanie składu słów
Dwa słowa są anagramami, jeśli jedno powstało z liter drugiego poprzez zmianę ich kolejności (np. "ekran" → "nerka"). W praktyce oznacza to, że oba napisy muszą mieć tę samą długość oraz dokładnie taki sam zbiór i liczbę liter.
def czy_anagram_sort(s1, s2):
if len(s1) != len(s2):
return False
return sorted(s1) == sorted(s2)
Złożoność czasowa: (wynika z szybkości sortowania).
from collections import Counter
def czy_anagram_count(s1, s2):
if len(s1) != len(s2):
return False
return Counter(s1) == Counter(s2)
Złożoność czasowa: (tylko jeden przebieg przez napisy).
Na maturze słowa w pliku dane.txt mogą być oddzielone tabulatorami lub mieć zbędne spacje na końcu. Zanim zaczniesz sprawdzać, czy słowa są anagramami, zawsze wykonaj na nich operację .strip().
Jeśli zadanie mówi, że wielkość liter nie ma znaczenia, dodaj również .lower(). Porównywanie "A" z "a" bez tej metody zawsze zwróci False.
Zanim uruchomisz ciężkie algorytmy sortowania, zawsze sprawdź najprostszy warunek: długość napisów. Jeśli len(s1) != len(s2), to napisy na pewno nie są anagramami. To "tanie" sprawdzenie, które pozwala pominąć zbędne obliczenia dla tysięcy błędnych par w pliku.
3
Szyfrowanie: Tablica ASCII, Cezar i Vigenère
Algorytmy kryptograficzne na maturze z informatyki opierają się na jednej kluczowej koncepcji: litery to tak naprawdę liczby zapisane w tablicy ASCII. Jeśli zrozumiesz, jak matematycznie manipulować tymi liczbami, napisanie dowolnego szyfru podstawieniowego zajmie Ci kilka minut.
Szyfrowanie polega na przesuwaniu liter. Aby dodać do litery wartość liczbową, musimy najpierw zamienić ją na kod ASCII.
ord(znak) – zwraca kod ASCII. Dla 'A' jest to 65, a dla 'Z' to 90.chr(kod) – zamienia liczbę z powrotem na znak.# Jak bezpiecznie zamienić 'A' (65) na pozycję 0 w alfabecie?
litera = 'C'
pozycja = ord(litera) - 65
print(pozycja) # Zwróci 2, bo 'C' jest trzecią literą alfabetu (0, 1, 2)
Każdy znak przesuwamy o stałą wartość klucza . Problem pojawia się na końcu alfabetu (np. przesunięcie 'Z' o 1 powinno dać 'A'). Rozwiązuje to genialny wzór z użyciem modulo 26 (ilość liter w alfabecie angielskim).
def cezar(tekst, k):
wynik = ""
for znak in tekst:
# 1. Zamień znak na pozycję od 0 do 25
poz = ord(znak) - 65
# 2. Przesuń i zawróć alfabet (modulo 26)
nowa_poz = (poz + k) % 26
# 3. Wróć do tablicy ASCII (dodaj 65)
wynik += chr(nowa_poz + 65)
return wynik
W Szyfrze Cezara kluczem jest jedna liczba (np. ). W szyfrze Vigenère'a kluczem jest słowo (np. "TAJNE"). Kolejne litery klucza decydują o tym, o ile przesunąć daną literę tekstu jawnego. Gdy klucz się kończy, powtarzamy go od początku.
def vigenere(tekst, klucz):
wynik = ""
for i in range(len(tekst)):
# Jakie jest przesunięcie 'k' w tym kroku?
# Modulo pozwala zapętlić klucz!
litera_klucza = klucz[i % len(klucz)]
k = ord(litera_klucza) - 65
# Reszta to klasyczny Cezar
poz = ord(tekst[i]) - 65
nowa_poz = (poz + k) % 26
wynik += chr(nowa_poz + 65)
return wynik
0, 1, 2.i % len(klucz)).Tip CKE: Czasami CKE narzuca, by ignorować w przesunięciach spacje (spacja nie zjada litery z klucza). Wtedy zamiast pętli for i in range... używamy osobnego ręcznego licznika indeks_klucza += 1.
Jeśli egzaminator poprosi Cię o odszyfrowanie wiadomości zaszyfrowanej Cezarem lub Vigenère'em, nie musisz pisać nowej funkcji! Wystarczy zmienić w kodzie jeden znak matematyczny. Przy zmiennej nowa_poz zmieniamy plus na minus:
nowa_poz = (poz - k) % 26.
Python doskonale radzi sobie z modulo na liczbach ujemnych i sam zawróci pozycję z powrotem na koniec alfabetu!
4
Wyszukiwanie wzorca: Algorytm Naiwny
Zadanie polega na znalezieniu wszystkich wystąpień krótkiego słowa (tzw. Wzorca, z ang. Pattern) wewnątrz długiego tekstu. Chociaż w Pythonie możesz to zrobić wbudowaną metodą, CKE regularnie sprawdza, czy rozumiesz matematyczne podwaliny tego procesu.
Polega na stworzeniu "okienka" o długości wzorca, które przesuwamy po tekście litera po literze. W każdym kroku sprawdzamy, czy wycinek tekstu pod okienkiem jest równy naszemu wzorcowi.
def szukaj_slicing(tekst, wzorzec):
licznik = 0
n = len(tekst)
m = len(wzorzec)
# Zatrzymujemy się, gdy do końca zostało mniej niż długość wzorca
for i in range(n - m + 1):
# Wycinamy fragment tekstu i porównujemy
if tekst[i : i + m] == wzorzec:
licznik += 1
return licznik
Wiele języków programowania nie obsługuje tak wygodnego slicingu. CKE często prosi o symulację z dwiema pętlami: zewnętrzna przesuwa wzorzec, a wewnętrzna sprawdza litera po literze.
def szukaj_klasycznie(tekst, wzorzec):
n = len(tekst)
m = len(wzorzec)
for i in range(n - m + 1):
zgodne = True
for j in range(m):
# Jeśli trafimy na różnicę, przerywamy pętlę wewnętrzną
if tekst[i + j] != wzorzec[j]:
zgodne = False
break
if zgodne:
print(f"Znaleziono na indeksie {i}")
Jeżeli w części praktycznej masz za zadanie wyłącznie policzyć ile razy wzorzec występuje w tekście (bez nakładania się na siebie, co jest standardem maturalnym), zrób to jedną wbudowaną funkcją:
tekst = "ABABABA"
ile_razy = tekst.count("ABA")
print(ile_razy) # Zwróci 2
Znasz już wszystkie techniki manipulacji stringami – od szyfrowania Cezara po analizę wystąpień wzorców. To potężna baza punktowa. Jesteśmy gotowi, by przejść do ostatniego technicznego etapu: Optymalizacji i Sortowania.
Przejdź do: Optymalizacja i Sortowanie ➡️