LeetCode 214. 最短回文串

LeetCode 214. 最短回文串
思路：

KMP算法，把s反转后记为t加到s的后面，中间以一个未出现的字符分隔，我们要找到最小的添加字符，转换角度就是找到最长的前缀回文串(回文串反转之后还等于本身)，而我们凑出来的字符串中找到最长的前缀回文串就是KMP算法的ne数组定义。所以最后ne[2 * n + 1](KMP 算法会在字符串的前面加上一个空格，为了方便处理下标)就是要找到的长度。

代码：

class Solution {
public:
    string shortestPalindrome(string s) {
        //KMP
        string t(s.rbegin(),s.rend());
        s = ' ' + s + '#' + t;
        int n = t.size();

        vector<int> ne(n * 2 + 2);

        for(int i = 2,j = 0;i <= n * 2 + 1;i++){
            while(j && s[i] != s[j + 1]) j = ne[j];
            if(s[i] == s[j + 1]) j++;
            ne[i] = j;
        }

        int len = ne[2 * n + 1];
        cout<<len<<endl;
        string left = s.substr(1,len),right = s.substr(len + 1,n - len);
        //cout<<left<<endl;
        //cout<<right;

        return string(right.rbegin(),right.rend()) + left + right;
    }
};