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

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

可以向一个给定字符串前添加字符，将其变成回文串，求最短的回文串。

本质可以理解为查找最长的前缀回文子串，

开始我的想法是暴力莽一波，O(n*n)复杂度,过了但很慢。

看到了更好的做法，用KMP，O(n)复杂度，哎，人老了，KMP调了好久。

将s和逆置的s拼接起来，用KMP求解next数组的方法，next数组表示的是到当前位置的后缀串与前缀串匹配的最长长度。

这样我们比较的构造串的前缀和后缀其实是s前缀和s前缀的逆置，因此就可以求出最长的前缀回文子串。

注意中间要加入没有出现的字符作为分隔，因为我们最长的前缀回文子串不能超过s本身的长度，如果出现”aaa“这种串，不加分隔符会导致最后的长度大于s的长度。

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

出处：http://blog.csdn.net/accepthjp/