|
Your task is, given an integer N, to make a palidrome (word that
reads the same when you reverse it) of length at least N. Any palindrome will do. Easy, isn't
it? That's what you thought before you passed it on to your inexperienced
team-mate. When the contest is almost over, you find out that that problem
still isn't solved. The problem with the code is that the strings generated
are often not palindromic. There's not enough time to start again from
scratch or to debug his messy code. Seeing that the situation is desperate,
you decide to simply write some additional code that takes the output and
adds just enough extra characters to it to make it a palindrome and hope for
the best. Your solution should take as its input a string and produce the
smallest palindrome that can be formed by adding zero or more characters at
its end.
|
|
||||||
|
|
Input
|
|
|
||||
|
|
Input will consist of several lines ending in EOF. Each line will contain
a non-empty string made up of upper case and lower case English letters
('A'-'Z' and 'a'-'z'). The length of the string will be less than or equal to
100,000. |
|
|||||
|
|
|
|
|||||
|
|
Output
|
|
|||||
|
|
For each line of input, output will consist of exactly one line. It should
contain the palindrome formed by adding the fewest number of extra letters to
the end of the corresponding input string. |
|
|||||
|
|
|
|
|||||
|
|
Sample
Input
|
Sample
Output
|
|
|
|
||
|
|
aaaa
abba amanaplanacanal xyz |
aaaa
abba amanaplanacanalpanama xyzyx |
|
|
|
||
|
|
| ||||||
martes, 26 de marzo de 2013
Extend to Palindrome
Suscribirse a:
Enviar comentarios (Atom)
Notese que el resultado que debe imprimirse contiene en la parte central un subpalindromo que es un sufijo de la palabra original,
ResponderEliminaren la mayor parte de los casos este consistira de una sola letra: la ultima.
Con ayuda de la funcion de fallo en la palabra invertida busco este "subpalindromo".
#include<stdio.h>
#include<string.h>
char a[100009];
long b[100009],l,i,j,k,h;
int main(){
while(scanf("%s",a)==1){
//printf("%s\n",a);
l=strlen(a);
b[l-1]=l-1;
b[l]=-2;
k=l-2;
l--;;
//printf("%ld ",k);
for(i=k;i>=0;i--){
j=b[i+1];
while(j!=-2&&j!=-1){
if(a[i]==a[j]){
b[i]=j-1;
j=-1;
}else{
j=b[j+1];
}
}
if(j==-2)
b[i]=l;
}
j=l;
l++;
for(i=0;i<l;i++){
while(j!=-2){
if(a[i]==a[j]){
j--;
break;
}else{
j=b[j+1];
}
}
if(j==-2)
j=l-1;
}
for(i=0;i<l;i++)
printf("%c",a[i]);
for(i=j;i>=0;i--)
printf("%c",a[i]);
printf("\n");
}
}