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

Solution:

public class Solution {
    public String shortestPalindrome(String s) {
        String str = s + "#" + new StringBuilder(s).reverse().toString();
        int[] table = new int[str.length()];
        for(int i=1; i<str.length(); i++){
            int j = table[i-1];
            while(j>0 && str.charAt(j)!=str.charAt(i)) j = table[j-1];
            table[i] = j + (str.charAt(j)==str.charAt(i) ? 1 : 0);
        }
        return new StringBuilder(s.substring(table[str.length()-1])).reverse().toString() + s;
    }
}