/**
title: problema do CeNPL'01: "Palindromizador" (proposta extra-aula)
ficheiro: cnpl01b.c autor: PRH versao de: 2001.04.29
.processamento de Strings em C;
.uso de arrays de caracteres para implementar strings
**/  

#include <stdio.h>
 
typedef char str[100];

char *palindromizador( str orig, int i, int j )
  { char *p, *p1, *p2;
    
    if ( i==j ) 
       { p = (char *)malloc(2); sprintf( p, "%c\0", orig[i] ); }
    else if ( j-i==1 ) 
       { if ( orig[i]==orig[j] )
            { p = (char *)malloc(3); sprintf( p, "%c \0", orig[i] ); }
         else 
            { p = (char *)malloc(3); sprintf( p, "%c%c\0", orig[i],orig[j] ); }
       }
    else 
       { if ( orig[i]==orig[j] )
            { p1 = palindromizador( orig,i+1,j-1 );
              p = (char *)malloc(strlen(p1)+1); 
              sprintf( p, "%c%s", orig[i],p1 ); 
            }
         else 
            { p1 = palindromizador( orig,i+1,j );
              p2 = palindromizador( orig,i,j-1 );
              if ( strlen(p1)<=strlen(p2) )
                 { p = (char *)malloc(strlen(p1)+1); 
                   sprintf( p, "%c%s", orig[i],p1 ); 
                 }
              else
                 { p = (char *)malloc(strlen(p2)+1); 
                   sprintf( p, "%c%s", orig[j],p2 ); 
                 }
            }
       }
    return( p );
  }

/*----- programa principal -----*/  
int main( )
{ int i,conta=0; 
  str pal; 
  char *palindroma;

  while ((scanf("%s",pal)) != 1) { ; }
  palindroma=palindromizador( pal, 0, strlen(pal)-1 ); 
  printf("Um possivel palindroma sera: "); 
    for (i=0; (palindroma[i]!='\0'); i++) 
        { if (palindroma[i]!=' ') { putchar(palindroma[i]); } }
    for (i=i-2; (i>=0); i--) { putchar(palindroma[i]); } 
  printf("\n"); 
  return(0); 
}