public class Solution {
public String shortestPalindrome(String s) {
StringBuilder sb = new StringBuilder();
sb.append(s).append('#').append(new StringBuilder(s).reverse());
int longestPal = getPrefixFunction(sb.toString());
StringBuilder res = new StringBuilder(s.substring(longestPal));
res.reverse().append(s);
return res.toString();
}
private int getPrefixFunction(String pattern) {
int len = pattern.length();
int[] pi = new int[len];
pi[0] = 0;
int matched = 0;
for (int i = 1; i < len; i++) {
while (matched > 0 && pattern.charAt(i) != pattern.charAt(matched)) {
matched = pi[matched - 1];
}
if(pattern.charAt(i) == pattern.charAt(matched)) {
matched++;
}
pi[i] = matched;
}
return pi[len - 1];
}
}