public String shortestPalindrome(String s) {
        if (s.length() <= 1) return s;
        String reverse = new StringBuilder(s).reverse().toString();
        String l = s + "#" + reverse;
        // now we have to find longest prefix that is equal to suffix from big string;
        int[] p = new int[l.length()];
        for (int i = 1; i < l.length(); i++) {
            int j = p[i - 1];
            while (j > 0 && l.charAt(i) != l.charAt(j))
                j = p[j - 1];

            if (l.charAt(i) == l.charAt(j))
                p[i] = j + 1;
        }
        return reverse.substring(0, s.length() - p[l.length() - 1]) + s;

    }
To solve this problem, we can use KMP algorithm
src/problems/hard/ShortestPalindrome.java