leetcode Question: Shortest Palindrome

Shortest Palindrome

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:

Although the logic of this question is not complicated, it is not easy to pass the OJ.
If you are familiar with famous string matching KMP algorithm, it would help a lot to solve the problem.

Let's first see the basic logic of this question. Given a string, out aim is to add a string in the front to make the new string a palindrome. Say the given string is \(S\), the string we add in the front is denoted as \(P\), so the result string is \(PS\), which needs to be a palindrome.  According to the definition of palindrome, we can rewrite string \(PS\) into:
$$ PS = PQP' $$, where \(QP' = S\) and \(P'\) is the reverse of string \(P\).
Note that, if \(PQP'\) is palindrome, \(Q\) must also be a palindrome. E.g., given a string "acecabcd", if we add a string "dcb",  the new string becomes  "dcbacecabcd", which is a palindrome. This string "dcbacecabcd" = "dcb" + "acecabcd", which can be rewritten as:
"dcb" + "acecabcd" = "dcb" + "aceca" + "bcd" = "dcb" + "aceca" + reverse("dcb"). Seen from this expression, string "aceca" is also a palindrome.

Let's see back to the question, now we have the string:
$$ PS = PQP' $$, we want \(P\) as short as possible, in other words, we want \(Q\) as long as possible. Thus, the question is now to compute the longest \(Q\)in string \(S\), subject to \(Q\) is a palindrome.


Next step is to compute longest palindrome start from the given string.  Brute-force is one way to solve it but it cannot pass the OJ. Recall the famous KMP algorithm, the failure function is to compute the longest suffix before current position that is also a prefix of the string. (more details see this post, which provides a very good explanation). In this question, we can easily convert the string to fit the the KMP failure function.

Say, we have string  $$ S = QP $$, we can append the reverse of \(S\) to \(S\): $$ SS' = QPP'Q' $$, remember that \(Q\)is a palindrome, \(Q=Q'\), therefore, we have: $$ SS' = QPP'Q $$, now we want to find the longest \(Q\), where \(Q\) is the prefix of \(SS'\), also a suffix of last position of \(SS\).

By applying to the failure function of KMP, we can get the result, but we have to pay attention that, the length of \(Q\) must less than \(S\) (half of \(SS'\)). In other words, we are only interested in the matching start from the second half of \(SS'\), that's why in line 19, 20 of my code, I keep the value as 0, so that the previous matching results will not effect the current matching.

Code(C++):

class Solution {
public:
    string reverse(string s){
        string res = "";
        for (int i=s.size()-1;i>=0;i--){
            res = res + s[i];
        }
        return res;
    }

    int failfunc(string s){
        int cnd = 0;
        int pos = 2;
        vector<int> t(s.size()+1,0);
        t[0] = -1;
        t[1] = 0;

        while (pos <= s.size()){
            if (pos ==s.size()/2){
                pos++;
            }else if (s[pos-1] == s[cnd]){
                cnd++;
                t[pos] = cnd;
                pos++;
            }else if (cnd > 0){
                cnd = t[cnd];
            }else{
                t[pos] = 0;
                pos++;
                cnd = 0;
            }
        }
        return t[s.size()];
    }

    string shortestPalindrome(string s) {
        int n = s.size();
        int m = failfunc(s + reverse(s));
        if (m >= s.size()){
            return s;
        }else{
            string q = s.substr(m);
            return reverse(q) + s;
        }
    }
};

Code(Python):

class Solution(object):
    
    def failfunc(self, s):
        ss = s + s[::-1]
        cnd = 0
        pos = 2
        t = [0 for x in range(len(ss)+1)]
        print t
        t[0] = -1
        
        while pos <= len(ss):
            if pos == len(s):
                pos += 1
            elif ss[pos-1] == ss[cnd]:
                cnd+=1
                t[pos] = cnd
                pos+=1
            elif cnd > 0:
                cnd = t[cnd]
            else:
                t[pos] = 0
                pos += 1
                cnd = 0
        return t[-1]
        
        
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return s
        m = self.failfunc(s)
        if m >= len(s):
            return s
        else:
            return s[m:][::-1]+s