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

My Thinking: This question only allows to add characters in the front. The resulting palindrome  might not be the optimal result.

For example "aabcb" should return "bcbaabcb" instead of "aabcbaa".

But this is a misleading. Solve for the optimal result will give you two cases. One is adding in the front, the other is adding in the back. We just pick the first one as the result.

Back to the question. Longest Palindromic Substring already gives a way to get the longest palindrome substring for each character position. Based on the array, we can extend the longest palindrome substring and get the optimal palindrome. But that might not be adding in the front. It doesn't matter. We should extend the longest palindrome that is nearest to position 0.

For example, "aabcb"->"#a#a#b#c#b#"
                                        12321214121
character 'c' has the longest palindrome coverage 4, but it's coverage does not cover position 0.

The largest coverage covering position 0 is the '#' between two 'a'. That's where we should extend from.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     // preprocessing  
     if(s == null || s.length()==0) return s;  
     s = preProcess(s);  
       
     // get longest palindrome substring  
     int[] range = new int[s.length()];  
     int pivot = 0;  
     range[0] = 1;  
     for(int i = 1;i < s.length();i++){  
       if(range[pivot]+pivot > i){  
         if(range[pivot] + pivot > range[2*pivot-i] + i)  
           range[i] = range[2*pivot-i];  
         else  
           range[i] = range[pivot]+pivot-i;  
       }  
         
       while(range[i]+i < s.length() && i-range[i] >= 0 && s.charAt(i+range[i])==s.charAt(i-range[i])) range[i]++;  
   
       if(range[pivot]+pivot < range[i]+i) pivot = i;  
     }  
       
     // extend based on the longest palindrome substring  
     while(pivot-(range[pivot]-1)!=0) pivot--;  
     s = reverse(s.substring(pivot+range[pivot], s.length())) + s;  
       
     // postprocessing  
     return postProcess(s);  
       
   }  
     
   private String reverse(String s){  
     return new StringBuilder(s).reverse().toString();  
   }  
     
   private String postProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++)  
       if(s.charAt(i)!='#') rslt.append(s.charAt(i));  
     return rslt.toString();  
   }  
     
   private String preProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       if(i==0) rslt.append("#");  
       rslt.append(s.charAt(i));  
       rslt.append("#");  
     }  
     return rslt.toString();  
   }  
 }