Test maturalny:  Operacje na tekstach

Palindrom

Napis, który czytany od końca jest identyczny z napisem czytanym od początku.

Sprawdzaj tylko do n / 2.

Antypalindrom

Napis parzystej długości, w którym żaden znak nie jest równy znakowi położonemu symetrycznie względem środka (definicja z zadania 6 Informatora CKE).

s[i] ≠ s[n − i + 1] dla i = 1, 2, …, n/2 (indeksy od 1).

Stos

Struktura LIFO — ostatni dodany element jest pierwszy do pobrania.

Naturalna dla wyrażeń nawiasowych i ONP.

Wyrażenie nawiasowe poprawne

Wyrażenie puste, złożenie dwóch poprawnych wyrażeń albo poprawne wyrażenie ujęte w parę nawiasów (definicja z zadania 2 Informatora CKE).

Dla jednego rodzaju nawiasów wystarczy licznik, dla kilku — stos; koszt O(n).

Szyfr Cezara

Szyfr podstawieniowy z przesunięciem alfabetu o stałą k.

Szyfrowanie: (c − 'A' + k) mod 26 + 'A'.

Szyfr podstawieniowy

Każdy znak alfabetu zamieniany na inny według klucza-permutacji.

Łamiemy analizą częstości znaków.

Histogram znaków

Tablica licząca wystąpienia każdego znaku w tekście.

Rozmiar 26 dla alfabetu łacińskiego, 256 dla ASCII.

Wyszukiwanie naiwne wzorca

Algorytm O(n·m) sprawdzający dopasowanie wzorca w każdej pozycji tekstu.

n — długość tekstu, m — długość wzorca.

Konkatenacja

Łączenie dwóch napisów — operator + w Pythonie i C++ string.

Kosztowna dla wielokrotnego doklejania (O(n²) naiwnie).

Substring

Spójny fragment napisu od indeksu i do j.

C++: s.substr(i, dl). Python: s[i:j].

Tokenizacja

Rozbicie tekstu na słowa po wybranym separatorze (spacja, tab).

Python: s.split(). C++: stringstream + getline.

Kod ASCII

Standardowe kodowanie znaków — 'A' = 65, 'a' = 97, '0' = 48.

Różnica 'a' − 'A' = 32.

1. 1 Naucz się trzech wzorców: palindrom z dwoma indeksami, wyrażenie nawiasowe z licznikiem albo stosem, szyfr Cezara z modulo.
2. 2 W zadaniach o częstości znaków zacznij od tablicy liczników — od razu widać najczęstszą literę.
3. 3 Ćwicz operacje na znakach w wybranym języku: w C++ isalpha, isupper, tolower, w Pythonie isalpha, isupper, lower. Umiej też obyć się bez nich — zadania z algorytmem zapisywanym w arkuszu zwykle zabraniają funkcji wbudowanych.
4. 4 Przy kilku rodzajach nawiasów używaj stosu; przy jednym wystarczy licznik, jak w zadaniu 2 Informatora CKE.
5. 5 Przy wyszukiwaniu wzorca pilnuj granicy pętli zewnętrznej: ostatnia dopuszczalna pozycja początku wzorca to n − m.
6. 6 Sprawdzaj programy na przypadkach brzegowych: pusty napis, jeden znak, same wielkie litery.
7. 7 Potem przejdź do odwrotnej notacji polskiej — korzysta z tego samego stosu.

Powiązane tematy

Te działy łączą się z tematem „Operacje na tekstach” – przećwicz je w Quizie.