Cacher is the code snippet organizer for pro developers

class Solution {
public:
    string shortestPalindrome(string s) {
        if (s == "") return s;
        string s2 = s;
        reverse(s2.begin(), s2.end());
        string news = s + "#" + s2;
        int n = news.size();
        vector<int> next(n+1);
        buildNext(news, next, n);
        if (next[n] > s.size()) {
            next[n] = (next[n] - s.size())*2;
        }
        string pres = s.substr(next[n]);
        reverse(pres.begin(), pres.end());
        return pres + s;
        
        // if(s == "")
        //     return s;
        // string s2 = s;
        // reverse(s2.begin(), s2.end());
        // string news = s + s2;
        // int n = news.size();
        // vector<int> next(n+1);
        // buildNext(news, next, n);
        // if(next[n] > s.size())
        //     next[n] = next[n] + 1 - s.size();
        // string pres = s.substr(next[n]);
        // reverse(pres.begin(), pres.end());
        // return pres + s;        
    }
    void buildNext(string& s, vector<int>& next, int n)
    {
        int k = -1;
        int j = 0;
        next[0] = -1;
        while(j < n)
        {
            if(k == -1 || s[j] == s[k])
            {
                k ++;
                j ++;
                next[j] = k;
            }
            else
            {
                k = next[k];
            }
        }
    }
};