214. Shortest Palindrome

using KMP

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        string tmp = s + "#" + rev;

        vector<int> next(tmp.size());
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < tmp.size(); i++) {
            while (k >= 0 && tmp[i] != tmp[k + 1])
                k = next[k];
            if (tmp[i] == tmp[k + 1]) k++;
            next[i] = k;
        }

        for (int i = 0; i < tmp.size(); i++) cout<<next[i]<<' ';cout<<endl;
        return rev.substr(0, s.size() - 1 - next[tmp.size() - 1]) + s;
    }
};

O(n^2)

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        string pre = "", suf = "";
        int overlap = 0;
        if (rev == s) return s;
        for (int i = 0; i < s.size(); i++) {
            pre += s[i];
            suf = rev[s.size() - i - 1] + suf;
            if (pre == suf) overlap = i;
        }
        return rev.substr(0, s.size() - overlap - 1) + s;
    }
};