Interview Question - use kmp

Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
Find the length of the shortest palindrome that you can create from S by applying the above transformation.

Answer:

Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.

prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.

int getPalindrome(string s) {
    int n = s.size();

    vector<int> p(2*n+1,0); 

    string current = s + '$';

    for (int i = 0; i < n; i++) {
        current += s[n - 1 - i];
    }

    p[0] = 0;
    for (int i = 1; i < 2 * n + 1; i++) {
        int j = p[i - 1];
        while (j > 0 && current[j] != current[i])
            j = p[j - 1];
        j += current[i] == current[j];
        p[i] = j;
    }
    return 2 *n - p[2 * n];//returns the length of the palindrome formed
}