This page explains Java solution to problem `Shortest Palindrome`

using `KMP`

algorithm.

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.

Input: "aacecaaa"Output: "aaacecaaa"

Input: "abcd"Output: "dcbabcd"

```
package com.vc.hard;
class ShortestPalindrome {
public String shortestPalindrome(String s) {
String sNew = s + "#" + reverse(s);
int[] kmp = new int[sNew.length()];
int n = sNew.length();
int start = 0, end = 1;
while(end < n) {
if(sNew.charAt(start) == sNew.charAt(end)) {
kmp[end] = start + 1;
start++;
end++;
}
else {
if(start == 0) kmp[end++] = 0;
else start = kmp[start - 1];
}
}
return reverse(s.substring(kmp[n - 1])) + s;
}
private String reverse(String s) {
int start = 0, end = s.length() - 1;
char[] cArr = s.toCharArray();
while(start < end) {
char ch = s.charAt(start);
cArr[start] = cArr[end];
cArr[end] = ch;
start++;
end--;
}
return new String(cArr);
}
}
```

O(N) Where

N is total number of elements in an input String

O(N) Where

N is total number of elements in an input String