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".

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

Hide Tags

String

Hide Similar Problems

(M) Longest Palindromic Substring (E) Implement strStr()

仔细分析一下会发现，问题的关键，在于找到从 s[0] 开始的最长回文串，
找到了之后把剩下的部分reverse一下，加在前面，就是答案。

既然是找最大回文，自然想到之前的 Longest Palindromic Substring 里用的“马拉车”Manacher 算法。
只需要在每次更新 center 和半径的时候，检查转换成 s 里的起点是否还是 0 就好了，一旦不是，就直接break；
这样就找到了从 s[0] 开始的最大回文串，后面就easy了。按照这个思路写了，8 ms，很不错。
后来在另一处看到：“Manacher算法的特性，id == p[id]时回文一定是从s[0]开始的”，试了一下，用这个判断也可以。

查了一下，不少提到利用 KMP 算法的帖子，想想也是，字符串查找么，KMP 是个不错的思路。
看了一下利用 KMP 的代码，很简洁，一时之间没看懂，要复习一下 KMP 的实现再看估计好些。
从这个帖子进去，还发现一篇“从头到尾彻底理解KMP（2014年8月22日版）”对 KMP 讲得非常仔细，回头一起学习下。

class Solution {
public:
    string shortestPalindrome(string s) {
        int len=s.length();
        if(!len || 1==len)
            return s;

        //Preprocessing of character to avoid even palindrome cases
        string buf = "$#";                                          //unique character as beginning
        for(int ii=0; ii<len; ++ii)
            buf += s[ii], buf += '#';                               //character as gapping
        buf += "&";                                                 //unique character as ending

        //linear calculation to find longest palindrome substring
        int lenb=buf.size(), mxx=0, pos=0;                          //mxx, pos are for final answer
        int lp[lenb], center=0, r=0;
        for(int ii=0; ii<lenb-1; ++ii)
        {
            int rr = center+r-1;                                    //explored right range
            lp[ii] = (rr>ii) ? min(lp[center-(ii-center)], rr -ii) : 0;

while(buf[ii+lp[ii]]==buf[ii-lp[ii]]) //scanning
lp[ii]++;

            if(ii+lp[ii]-1 > rr)                                    //exploring new right range
            {
                center=ii, r=lp[ii];                                //update new center and radius

                if(ii==lp[ii] && mxx<r)                             //only check starting from s[0]
                {
                    //if(0<(ii-r)/2)                                //exit if beginning is not s[0]
                    //    break;
                    mxx=r, pos=ii;                                  //update longest and its center
                }
            }
        }

        int plen=mxx-1;                                             //length of palindrome from s[0]
        string addme = (plen==len) ? "" : s.substr(plen, len-plen); //get the rest part of s
        reverse(addme.begin(), addme.end());                        //reverse the rest part
        return addme+s;                                             //return combined string
    }
};
8 ms.