Algorytmy na tekstach: palindromy, anagramy i wyszukiwanie wzorca

Zadania na tekstach to stały element części praktycznej matury z informatyki: plik zawiera słowa lub napisy, a ty masz policzyć palindromy, znaleźć pary anagramów albo wystąpienia wzorca. Podstawa programowa wymienia algorytmy porównywania tekstów i wyszukiwania wzorca w tekście metodą naiwną — ten materiał ćwiczy je razem z dwoma klasycznymi problemami, które z nich wynikają: palindromami i anagramami.

Palindrom sprawdzasz na dwa sposoby: porównując napis z jego odwróceniem albo przesuwając dwa indeksy od końców do środka — wtedy wystarcza $\lfloor n\mathrm{/}2\rfloor$ porównań. Śledzisz krótki program w Pythonie i zwracasz uwagę na przypadki brzegowe, na przykład napis jednoznakowy.

Anagramy to napisy złożone z tych samych liter w tych samych liczbach. Porównujesz dwie metody: sortowanie liter obu napisów (czas $O(n\log n)$) i zliczanie wystąpień liter w tablicy 26 liczników (czas $O(n)$), a potem przewidujesz wynik programu, który porównuje takie tablice.

Wyszukiwanie wzorca metodą naiwną polega na sprawdzeniu każdego z $n-m+1$ możliwych położeń wzorca długości $m$ w tekście długości $n$. Liczysz wystąpienia, także nakładające się, wskazujesz pozycje (indeksowane od zera) i uzasadniasz złożoność $O(n\cdot m)$. Funkcja w C++ pokazuje, jak warunek pętli decyduje o tym, czy sprawdzone zostaną wszystkie położenia.

Ostatni wątek to porządek leksykograficzny: napis będący początkiem dłuższego jest od niego mniejszy, a przy porównywaniu według kodów ASCII wielkie litery poprzedzają małe — to częste źródło błędów przy sortowaniu słów w programie.

Materiał oferuje cztery formy pracy. Quiz zawiera pytania o metody i złożoność oraz analizę programów z wyjaśnieniem każdego kroku. Fiszki utrwalają definicje, metody i złożoności. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz opisać algorytm własnymi słowami i dobrać metodę do zadania. Praca pisemna do wydruku zawiera zadania otwarte: ręczne śledzenie algorytmów i zapis funkcji w pseudokodzie lub w wybranym języku programowania (C++, Python lub Java).

Wszystkie zadania są oryginalnymi ćwiczeniami do samodzielnej nauki, a wyniki programów zostały sprawdzone przez ich uruchomienie.

• Sprawdzasz, czy napis jest palindromem, i liczysz potrzebne porównania.
• Rozpoznajesz anagramy i porównujesz metodę sortowania z metodą zliczania liter.
• Wykonujesz naiwne wyszukiwanie wzorca, także z wystąpieniami nakładającymi się.
• Uzasadniasz złożoność O(n · m) naiwnego wyszukiwania wzorca.
• Porównujesz napisy w porządku leksykograficznym z uwzględnieniem kodów ASCII.

Materiał ćwiczeniowy przygotowany przez Zestly.