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

Naive solution is remove the right-most letters of string one by one and check whether the remaining part is palindrome. It exceeds time limit. The fancy solution is to use KMP.

1:  public class Solution {  
2:    public String shortestPalindrome(String s) {  
3:      String ss = s + "#" + new StringBuilder(s).reverse().toString();  
4:      int[] pie = new int[ss.length()];  
5:      int k = 0;  
6:      pie[0] = 0;  
7:      for(int i = 1; i < ss.length(); i++) {  
8:        while(k>0 && ss.charAt(k) != ss.charAt(i))  
9:          k = pie[k-1];  
10:        if(ss.charAt(k) == ss.charAt(i))  
11:          k++;  
12:        pie[i] = k;  
13:      }  
14:      return (new StringBuilder(s.substring(pie[ss.length()-1])).reverse().toString()+s);  
15:    }  
16:  }