Shortest Palindrome -- LeetCode

[Question]

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

[Analysis]
The key is to find the longest palindrome sub-string S', starting from position 0, in S, the solution will be to place the reversed (S - S') in front of S. For example, in "aacecaaa", the longest palindrome sub-string from the beginning is, "aacecaa"; therefore, inserting one "a" is the solution.

The naive way to find the longest sub-string is at O(N^2), in which going through each index of string S and checking whether S[0]...S[i] is a palindrome.

An optimized solution is to apply KMP algorithm. First, reverse S as S" and construct one larger string S+'*'+S" -- '*' serves as a separator. Secondly, apply KMP algorithm and build a table A for the longest repetitive pattern (from the beginning) for the long string. Apparently, the last element of A indicates the length of longest palindrome sub-string of S, starting from index 0.

The time and space complexity both are O(N).

[Solution]

class Solution {
    public:
    void kmpTable(string& p, vector<int>& next) {
        next[0]=0;
        int j=1; int k=0;

        while (j<p.size()) {
            if (p[j]==p[k]) {
                next[j] = k+1;
                j++; k++;
            }
            else {
                if (k!=0) k= next[k-1];
                else ++j;
           }

        }
    }

    string shortestPalindrome(string s) {
        string s1 = s;
        reverse(s1.begin(), s1.end() );
        string str = s+"*"+s1;

        vector<int> v(str.size(), 0);
        kmpTable(str, v);

        string r = s.substr(v.back());
        reverse(r.begin(), r.end());

        return r+s;
    }
};