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_nb₁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<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstdio>
 7 #include<queue>
 8 #include<vector>
 9 #include<stack>
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<n;i++)
26       cout<<str[i];
27      for(i=1;i<n;i++)
28       if(judge(i))
29        break;
30     for(j=i-1;j>=0;j--)
31      cout<<str[j];
32     cout<<endl;
33     return 0;
34 
35 
36  }

View Code