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

public class Solution {
    public String shortestPalindrome(String s) {
        if(s.length() <=1) return s;
        String reverse = (new StringBuilder(s)).reverse().toString();
        String target = s + "*" + reverse;
        int[] next = new int[target.length()];
        next[0] = 0;
        for(int i=1; i< target.length(); i++){
            int k = next[i-1];
            while(k>0 && target.charAt(k) != target.charAt(i)) k = next[k-1];
            next[i] = target.charAt(k) == target.charAt(i) ? k+1 : k;
        }

        return reverse.substring(0, reverse.length()-next[target.length()-1]) + s;
    }
}