The idea is to concat s and reverse s. Then compute the longest prefix which is also suffix.

```
public class Solution {
public String shortestPalindrome(String s) {
int len = computeLPS(s+reverse(s));
if(len >= s.length()) return s;
return reverse(s.substring(len))+s;
}
//longest proper prefix which is also suffix
public int computeLPS(String s){
int[] lps = new int[s.length()]; // lps[0] is 0
int len = 0;// lenght of the previous longest prefix suffix
int i=1;
while(i<s.length()){
if(s.charAt(i) == s.charAt(len)){
len++;
lps[i] = len;
i++;
}else {
if(len != 0){
len = lps[len-1];
}else {
lps[i] = 0;
i++;
}
}
}
return len;
}
public String reverse(String s){
String res="";
for(int i=s.length()-1;i>=0;i--){
res+=s.charAt(i);
}
return res;
}
}
```

**[1]: http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/**