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 == null || s.length() == 0) {
        	return "";
        }
        String copy = s;
        StringBuffer stringBuffer = new StringBuffer(s);
        StringBuffer reverse = stringBuffer.reverse();
        s = reverse.toString();
        char[] charArr = manacherString(s);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int max = -1;
        for (int i = 0; i < pArr.length; i++) {
        	pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
        	while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
        		if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
        			pArr[i]++;
        		} else {
        			break;
        		}
        	}
        	if (i + pArr[i] > pR) {
        		pR = i + pArr[i];
        		index = i;
        	}
        	if (pR == charArr.length) {
        		max = pArr[i];
        		break;
        	}
		}
        char[] tmp = new char[s.length() - max + 1];
        for (int i = 0; i < tmp.length; i++) {
        	tmp[tmp.length - 1 - i] = charArr[i * 2 + 1];
		}
        return new StringBuffer(new String(tmp)).reverse() + copy;
    }

	private char[] manacherString(String s) {
		// TODO Auto-generated method stub
		char[] charArray = s.toCharArray();
		char[] res = new char[s.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i < res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArray[index++];
		}
		return res;
	}
}