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

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

public class Solution {
    public String shortestPalindrome(String s) {
       if(s.length() <= 1){ return s; }
        String curs = s + " " + new StringBuilder(s).reverse().toString();
        int[] trace = new int[curs.length()];
        for(int i = 1 ; i < curs.length() ; i++){
            int curindex = trace[i-1];
            while(curindex > 0 && curs.charAt(curindex) != curs.charAt(i)){
                curindex = trace[curindex-1];
            }
            if(curs.charAt(curindex) == curs.charAt(i)){
                trace[i] = curindex+1;
            }
        }
        return new StringBuilder(s.substring(trace[curs.length()-1])).reverse().toString() + s;
    }
}

http://blog.csdn.net/v_july_v/article/details/7041827