题目：

Shortest Palindrome

 

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

分析：

利用进行求解。时间复杂度O(n)。空间复杂度O(n).

class Solution {public:    string shortestPalindrome(string s) {        if(s.size()<=1)            return s;              string str(s.size()*2+1,'#');        for(int i=0,j=1;i
     

p(size,1); p[1]=2; for(int i=2;i<=size/2;++i) { int maxright=p[id]+id-1; if(i>maxright) { //注意检查越界 while(i - p[i]>=0 && str[i+p[i]]==str[i-p[i]]) ++p[i]; } else { int idleft=id-p[id]+1; int k=i-id,j=id-k,tmp=j-p[j]+1;//i和j关于id对称 if(tmp>idleft) p[i]=p[j]; else if(tmp

=0 && str[i+p[i]]==str[i-p[i]]) ++p[i]; } } if(p[i]+i>p[id]+id) id=i; if(i-p[i]+1==0) res=i; } if (res == s.size()) return s; else { string tmp = string(s.begin() + res, s.end()); reverse(tmp.begin(), tmp.end()); return tmp + s; } }};