1354. Palindrome. Again Palindrome

Time limit: 1.0 second Memory limit: 64 MB

A

 

word

 is the nonempty sequence of symbols

 

a

₁

a

₂…

a_n. A

 

palindrome

 is the word

 

a

₁

a

₂…

a_n

 that is read from the left to the right and from the right to the left the same way (

a

₁

a

₂…

a_n

 =

 

a_na

_n−1…

a

₁). If

 

S

₁

 =

 

a

₁

a

₂…

a_n

 and

 

S

₂

 =

 

b

₁

b

₂…

b_m, then

 

S

₁

S

₂

 =

 

a

₁

a

₂…

a_n

b

₁

b

₂…

b_m. The input contains some word

 

S

₁. You are to find a nonempty word

 

S

₂

 of the minimal length that

 

S

₁

S

₂

 is a palindrome.

Input

The first input line contains

 

S

₁

 (it may consist only of the Latin letters). It’s guaranteed that the length of

 

S

₁

 doesn’t exceed 10000 symbols.

Output

S

₁

S

₂.

Samples

input	output
No	NoN
OnLine	OnLineniLnO
AbabaAab	AbabaAababA

Problem Author: Denis Nazarov

Problem Source: USU Junior Championship March'2005

***************************************************************************************

kmp没想出来，用简单法做的

***************************************************************************************

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 #include
              
                8 #include
               
                 9 #include
                
                 10 using namespace std;11 char str[10011];12 int n,i,j,k;13 bool judge(int x)//检查后缀的最大回文14 {15 int h,g;16 for(h=x,g=n-1;g>h;h++,g--)17 if(str[h]!=str[g])18 return false;19 return true;20 }21 int main()22 {23 scanf("%s",str);24 n=strlen(str);25 for(i=0;i
                 
                  =0;j--)31 cout<