Shortest Palindrome

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".

Anaylysis

An easy approach to tackle this question is to find the longest prefix of S that's already a palindrome, therefore we can add the reversed string of remaining part in front of it to form the shortest palindrome in all.

The question becomes how to find the longest prefix of S that's already a palindrome.

Here we can apply the KMP Algorithm to find the answer.

We construct an new String ss = s + "$" + reverse(s) + "#". Using the sub-function next() to find the longest prefix which is also a suffix of ss. Therefore this prefix is the longest prefix that's also a palindrome in s.

Solution

public String shortestPalindrome(String s) {
        if(s==null || s.length()<2) return s;
        String ss=s+"$"+new StringBuilder(s).reverse().toString()+"#";
        int next=next(ss);
        return new StringBuilder(s.substring(next)).reverse().append(s).toString();
    }

    public int next(String s){
        int slen=s.length();
        int[] next=new int[slen];
        char[] chars=s.toCharArray();
        next[0]=-1;
        int i=0, j=-1;
        while(i<slen-1){
            if(j==-1 || chars[i]==chars[j]) next[++i]=++j;
            else j=next[j];
        }
        return next[slen-1];
    }