Palindrom

Palindrom — sprawdzanie i generowanie

Palindrom to tekst, który czyta się tak samo od przodu i od tyłu. Klasyczne przykłady to „kajak”, „kobyła ma mały bok” czy liczby jak 12321.

Jak sprawdzamy?

Przykład

„Kobyła ma mały bok” po usunięciu spacji i wielkości liter daje „kobylamamalybok”, który czytany od tyłu wygląda identycznie. To palindrom.

Generowanie palindromu

Aby z dowolnego tekstu zbudować palindrom, doklejamy jego lustrzane odbicie (bez ostatniej litery). Np. z „abc” powstaje „abcba”, a z „kot” — „kotok”.

Jak działa narzędzie: normalizacja, porównanie i konstrukcja

Sprawdzanie palindromu to porównanie tekstu z jego odwróceniem. Narzędzie robi to znak po znaku od dwóch końców: ustawia jeden wskaźnik na pierwszym znaku, drugi na ostatnim, a potem porównuje je ze sobą. Jeśli znaki się różnią, napis nie jest palindromem i sprawdzanie kończy się w tym miejscu. Jeśli są równe, wskaźniki przesuwają się o jedną pozycję do środka. Gdy się miną lub spotkają, tekst jest palindromem. Liczba porównywanych par wynosi n div 2, gdzie n to długość tekstu po normalizacji — przy długości nieparzystej środkowy znak nie ma pary, przy parzystej pary tworzą wszystkie znaki.

Przed porównaniem tekst może przejść normalizację. Pierwszy przełącznik usuwa spacje oraz znaki, które nie są literami ani cyframi, drugi sprowadza całość do małych liter. Oba są opcjonalne, więc ten sam napis wypadnie raz jako palindrom, a raz nie — decyduje o tym konfiguracja, a nie sam tekst. Normalizacja dotyczy wyłącznie porównania i nie zmienia tego, co wpisałeś w polu wejściowym.

Generowanie działa odwrotnie: nie sprawdza, czy tekst jest palindromem, tylko zawsze taki tworzy. Narzędzie bierze napis wejściowy, odrzuca jego ostatni znak, odwraca resztę i dokleja ją na końcu. Dla tekstu o długości n powstaje napis o długości 2 * n - 1, bo doklejanych znaków jest n - 1. Wynik jest palindromem z definicji — konstrukcja gwarantuje symetrię nawet wtedy, gdy wejście w ogóle nie było symetryczne.

Przykład krok po kroku: liczba 12321

1. Wpisujemy tekst 12321. Długość wejścia wynosi n = 5 znaków.
2. Sprawdzanie: wskaźniki startują na pierwszej i ostatniej pozycji, normalizacja nie ma tu nic do roboty, bo w napisie nie ma spacji ani wielkich liter.
3. Para pierwsza: pozycja 1 to znak 1, pozycja 5 to znak 1. Znaki są zgodne, wskaźniki przesuwają się do środka.
4. Para druga: pozycja 2 to znak 2, pozycja 4 to znak 2. Znaki są zgodne, wskaźniki przesuwają się dalej.
5. Zostaje pozycja 3 ze znakiem 3. Dla n = 5 liczba par to 5 div 2 = 2, więc środkowy znak nie ma pary i nie bierze udziału w porównaniu.
6. Niezgodności jest 0, więc 12321 jest palindromem. Generowanie z tego samego wejścia: odrzucamy ostatni znak, zostaje 1232, odwracamy na 2321 i doklejamy, co daje 123212321 o długości 9, czyli 2 * 5 - 1.

Tabela referencyjna: wynik generowania dla różnych wejść

Jak używać narzędzia w praktyce

• Najpierw ustal, czy spacje i znaki mają się liczyć. Dla zdań włącz usuwanie spacji i interpunkcji, dla pojedynczych wyrazów zwykle nie ma to znaczenia, ale wynik sprawdzenia może się przez to różnić.
• Do zdań włącz też ignorowanie wielkości liter. Bez tego pierwsza wielka litera na początku zdania od razu przerwie porównanie i otrzymasz wynik negatywny mimo symetrycznego układu znaków.
• Sprawdzaj i generuj w dwóch osobnych krokach. Najpierw ustal wynik sprawdzenia, a dopiero potem użyj generatora — to dwie różne operacje i nie warto ich mieszać w jednym przebiegu.
• Kontroluj długość wyniku przed wklejeniem go dalej. Dla wejścia o długości n generator zwraca 2 * n - 1 znaków, więc długi tekst wejściowy daje napis niemal dwukrotnie dłuższy.
• Testuj krótkimi napisami. Jednoznakowy tekst zwraca sam siebie, a dwuznakowy daje wynik o długości 3 — takie próby szybko potwierdzają, że rozumiesz zasadę działania.

Ograniczenia i pułapki

• Normalizacja nie zamienia znaków diakrytycznych. Litera ł i litera l to dwa różne znaki, podobnie ą i a. Jeśli porównujesz tekst z pominięciem wielkości liter, nie oznacza to jeszcze, że różnice w znakach diakrytycznych znikną.
• Usuwanie znaków zmienia sens sprawdzenia. Gdy odfiltrujesz cyfry, interpunkcję albo spacje, porównujesz już inny napis niż ten, który widzisz. To bywa zamierzone, ale potrafi też odwrócić wynik.
• Symetria znakowa to nie symetria słowna. Narzędzie porównuje znaki, a nie wyrazy, więc zdanie czytane od tyłu słowo po słowie ma inną własność niż ten sam tekst czytany znak po znaku.
• Generator nie pilnuje sensu ani czytelności. Każdy wynik jest palindromem, ale przy dłuższych wejściach staje się długim ciągiem znaków bez znaczenia i bez podziału na wyrazy.

Najczęstsze pytania