class Solution {
public:
    vector<int> getpmt(string l){
        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];
            p[i] = (j += l[i] == l[j]);
        }
        return p;
    }

    string shortestPalindrome(string s) {
        if(s.length()==0)
            return s;
        string rs=s;
        reverse(rs.begin(), rs.end());
        string ls = s+"#"+rs;
        vector<int> pmt = getpmt(ls);
        int t = pmt[ls.length()-1];
        string substr = s.substr(t, s.length()-1);
        reverse(substr.begin(), substr.end());
        string res = substr+s;
        return res;
    }
};