题目来源
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".

第一想法就是找最长的0-i的回文，然后补上后面的就行。
然后进一步的想法就是找字符串中第一个字母出现的位置，判断其是不是回文。
如下，但是超时了。

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        if (n == 0)
            return "";
        int cut = 0;
        for (int i=1; i<n; i++) {
            if (s[i] == s[0] && isPalindrome(s.substr(0, i+1))) {
                cut = max(cut, i);
            }
        }
        string t = s.substr(cut+1);
        reverse(t.begin(), t.end());
        return t + s;
    }
    
    bool isPalindrome(string s)
    {
        int l = 0, r = s.length()-1;
        while (l < r) {
            if (s[l] == s[r]) {
                l++;
                r--;
            }
            else
                return false;
        }
        return true;
    }
};

看了下答案，巧妙的利用了KMP算法算出最长的0-i的回文，只需要O(n)的复杂度。什么是KMP？可以看看阮一峰老师的博客。

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        if (n == 0)
            return "";
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string new_s = s + '#' + rev_s;
        vector<int> p(2*n+1, 0);
        for (int i=1; i<2*n+1; i++) {
            int j = p[i-1];
            while (j > 0 && new_s[i] != new_s[j])
                j = p[j-1];
            p[i] =(j += new_s[i] == new_s[j]);
        }
        string t = rev_s.substr(0, n-p[2*n]);
        return t + s;
    }
};