public class Solution {
    public String shortestPalindrome(String s) {
        int[] pi = new int[s.length()];
        for (int i=1; i<pi.length; i++) {
            int j = pi[i-1];
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = pi[j-1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            pi[i] = j;
        }
        int j = 0;
        for (int i=s.length()-1; i>=0; i--) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = pi[j-1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
        }
        return new StringBuilder(s.substring(j)).reverse().append(s).toString();
    }
}