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

例子

Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

分析

方法一

穷举法，枚举N种情况，判断每种情况的字符串是不是回文字符串。

方法二

kmp算法

要点

kmp算法

时间复杂度

方法一

O(n^2)

方法二

O(n)

空间复杂度

方法一

O(1)

方法二

O(n)

代码

方法一

class Solution {
public:
    string shortestPalindrome(string s) {
        if (isPalindrome(s)) return s;
        string res, tail;
        for (int i = s.size() - 1; i >= 1; i--) {
            tail += s[i];
            res = tail + s;
            if (isPalindrome(res)) return res;
        }
        return s;
    }
    
private:
    bool isPalindrome(const string &s) {
        for (int i = 0; i < s.size() / 2; i++)
            if (s[i] != s[s.size() - i - 1]) return false;
        return true;
    }
};

方法二

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