#include <stdio.h>

#define min(a,b) ((a<b)?a:b)

char input[1024];	/* vnitřní representace bez mezer, velkých písmen\dots */
int  len[1024];		/* délky nejdelších palindromů s~pevnými středy */

char original[1024];	/* uživatelská representace -- indexuje se od jedničky */
int  offset[1024];	/* tabulka převádějící indexy vnitřní na indexy vnější representace */
int orig_counter  = 0;
int token_counter = 0;

int longest = 1;	/* index středu (zatím) nejdelšího palindromu */

void summary(void)
{
	int i;
	printf("Nejdelsi nalezeny palindrom jest: ");
	for (i = offset [ longest - len[longest] + 2 ]; i < offset [ longest + len[longest] - 2 ]; i++) 
		putchar(original[i]); 
	printf("\n");
	exit(0);
}

void get_text_and_make_tokens(void)
{
	char c;
	input[0] = ' ';		/* zarážka -- nebude se rovnat ničemu dalšímu */
	original[0] = ' ';	/* hlavně ne `c', hrozilo by falešné `ch' */

	do {
		c = getchar();			/* další znak ze~vstupu */
		original[++orig_counter] = c;	/* ukládej původní tvar */
		if (c >= 'A' && c <= 'Z')
			c += 'a' - 'A';		/* velká písmena na malá */
		if (c == 'h' && original[orig_counter-1] == 'c') {
			input[++token_counter] = 'C';	/* `ch' je token */
			continue;			/* a znova */
		}
		if (c == ' ') continue;			/* mezera? znova */
		input[++token_counter] = c;
		input[++token_counter] = '-';		/* uloží tvar a \dots */
		offset[token_counter] = orig_counter;	/* kde hledat originál */
	} while (c != EOF);	/* opakuj, dokud je co číst */
	input[++token_counter] = '-';	/* $\leftarrow$ co by bez tohoto řádku drhlo? */
}

void main()
{
	int rightmostcentre = 1;	/* kam nejdál doprava se někdo dostal */
	int rightmostedge = 1;
	int i = 0;		/* vzdálenost od středu */
	int centre = 1;		/* právě zpracovávaný střed */
	
	get_text_and_make_tokens();

	while (1) {
		while (input[centre - i] == input[centre + i]) ++i;
		len[centre] = i;			  /* palindrom délky $2i+1$ */
		if (rightmostedge < centre + i) {
			rightmostedge = centre + i - 1;
			rightmostcentre = centre;
		}
		if (i > len[longest]) longest = centre;
		if (input[rightmostedge] == 0)  summary();    /* dosáhli jsme na konec */
		centre++;
		if (rightmostedge < centre) i = 1;
		else i = min(len[2 * rightmostcentre - centre], rightmostedge - centre);
		/* právě jsme využili zrcadlení, ale nanejvýš na hranici */
	}
}