214

class Solution {
public:
    vector<int> lps;
    void kmpPreprocess(string pat){
        int n=pat.size(), i=0, j=-1;
        lps.resize(n+1, 0);
        lps[0] = -1;
        while(i<n){
            while(j>=0 && pat[i] != pat[j])
                j = lps[j];
            i++; j++;
            lps[i] = j;
        }
    }


    string shortestPalindrome(string s) {
        if(s == "") return "";
        string pat = s;
        reverse(s.begin(), s.end());

        int n = s.size();
        kmpPreprocess(pat+"#"+s);
        int len = n-lps.back();
        return s.substr(0, len)+pat;
    }
};