Palindrom tekstowy

---

Zadanie 5. Napisz program, który określi czy wczytany ciąg jest palindromem tekstowym.

Uwaga!!! Palindromem nazywamy wyraz, który czytany z lewej do prawej jest taki sam jak z prawej do lewej np.:

kajak

kobyłamamałybok

 

Dane wejściowe

Pierwszy wiersz składa się z jednej liczby n<10000, który określa ilość zestawów danych.

Każdy zestaw danych opisany w osobnym wierszu składa się z jednego wyrazu nie dłuższego niż 100 małych liter języka angielskiego.

Dane wyjściowe

Dla każdego zestawu danych wypisz słowo tak, jeśli dany ciąg jest palindromem, w przeciwnym wypadku wypisz nie.

Przykład

Wejście

3

adam

kobylamamalybok

sedes

Wyjście

nie

tak

tak

Program można testować na automatycznej sprawdzarce tutaj

Rozwiązanie.

#include <iostream>
#include <cstring>

using namespace std;

bool czy_palindrom(char tab[])
{
	int dl; //zmienna przechowuje długość wczytanego wyrazu
	dl = strlen(tab); //strlen zwraca ilość znaków w tablicy tab
	--dl; //zmniejszenie wartości zmiennej dl, w celu wskoczenia
			// na ostatni indeks tablicy
	for(int i=0;i<=dl/2;i++)
	  if(tab[i]!=tab[dl-i]) //jeśli odpowiednie litery nie będą się zgadzać
	  	return false;		//funkcja zwróci false
	  	
	return true; //gdy wszystkie litery będą się zgadzać 	
}

int main()
{
	int t; /*zmienna określa ilość zestawów danych*/
		
	char wyraz[101]; //zmienna przechowuje wczytany wyraz
	
	cin>>t; //wczytanie liczby testów
	
	while(t--) //pętla odpowiedzialna za wczytanie zestawów danych
	{
		cin>>wyraz;
		
		if(czy_palindrom(wyraz)) //lub if(czy_palindrom(wyraz == true)
		   cout<<"tak"<<endl;
		else
		   cout<<"nie"<<endl;
		
	}
	   
	return 0;
}

Przykładowe dane wejściowe:

5
kobylamamalybok
kaftan
kajak
preeeeeeeerp
a

 

Dane wyjściowe:

tak
nie
tak
tak
tak

 

Objaśnienie.

Rozpatrzmy słowo kajak. Popatrzmy jak przechowywane są kolejne litery tego wyrazu:

k - 0

a - 1

j - 2

a - 3

k - 4

Żeby słowo było palindromem pierwszy znak musi być równy ostatniemu, drugi przedostatniemu itd. Czyli:

tab[0] = tab[4]

tab[1] = tab[3]

dalej nie trzeba sprawdzać

Zauważmy, że gdy do zmiennej dl przypiszemy długość słowa kajak (liczbę 5) i zmniejszymy ją o 1, to będzie pasowała ona jako ostatni numer komórki tablicy. Teraz przy każdym przejściu pętli początek zwiększamy o wartość licznika i, a koniec zmniejszamy wskakując na odpowiednie litery do porównania (tab[i] = tab[dl-i]). Warto zauważyć, że pętla powinna wykonać się nie więcej niż połowę długości wyrazu o parzystej ilości znaków i w naszym przypadku $$iloscznakow\ div\ 2$$ dla nieparzystej ilości znaków (nie musimy wykonywać dodatkowego odejmowania w tablicy).