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

实际上，我们可以将上面的字符串进行反转，然后连接在一起，一定是一个回文，但是并不以一定是最短的，这就要求我们求出反转的字符串的后缀与源字符串的最长匹配，举个例子:
原字符串:aacecaaa       反转后字符串: aaacecaa
他俩的后缀与前缀的最长匹配为aacecaa，将原字符串与反转后字符串连接起来，求出新字符串的前缀数组(KMP)，连接时，最好用一个特殊字符连接，不然会出现
源字符串aaaaa          反转后字符串aaaaa

aaaaaaaaaa,那么最后的结果是9，显然不满足结果

class Solution {
public:
    string shortestPalindrome(string s) {
        string reversed(s);
        reverse(reversed.begin(), reversed.end());

        string l = s + "#" + reversed;
        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];
            if(l[i] == l[j])
                j = j + 1;
            p[i] = j;
        }

        return reversed.substr(0, s.size() - p[l.size() - 1]) + s;
    }
};