uva11475 - Extend to Palindrome
题面：
11475 - Extend to Palindrome
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
aaaa
abba
amanaplanacanal
xyz
Sample Output
aaaa
abba
amanaplanacanalpanama
xyzyx
题意分析：
给你一个字符串，要你添加一些字符使串成为回文串，所添加的字符要最少。
思路：
可以用原字符串的倒置字符串与原字符串匹配（KMP)，将倒置串作为模式串P，匹配到文本串（原串）最后时，则此时模式串匹配到的位置的前缀是一个回文子串，要使整个原串是回文的，只需将原串加上模式串后边没匹配的字符即可。
eg:
t :amanaplanacanal
p:lanacanalpanama
当整个串匹配完时，最后匹配情况就是加粗部分,容易验证匹配部分一定是回文的。此时只需要在原串后加上P串后面没匹配的字符就可使整个字符串成为回文串。
实现：
#include<bits/stdc .h>#define ll long longtypedef unsigned long long ull;using namespace std;const int Max=1e6 20;const int Maxn=1e7 20;const int mod=1e9 7;const int c=231;inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;} while(ch<'0'||ch>'9'); do{x=x*10 ch-'0';ch=getchar();} while(ch>='0'&&ch<='9');return x*f;}int Next[Max];void fuck(string str)//得到Next数组{ int j; int strl=str.size(); for(int i=1;i<strl;i ) { j=Next[i-1]; while(j>0&&str[i]!=str[j]) j=Next[j-1]; if(str[i]==str[j]) j ; Next[i]=j; }}int main(){ string s,rs; while(cin>>rs) { int slen=rs.size(); int ans=-1; s=rs; reverse(rs.begin(),rs.end()); fuck(rs); int j=0; for(int i=0;i<slen;i ) { while(j>0&&s[i]!=rs[j]) j=Next[j-1]; if(s[i]==rs[j]) j ; ans=j; } cout<<s; for(int i=slen-ans-1;i>=0;i--) cout<<s[i]; cout<<endl; } return 0;}