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.

For example:

Given"aacecaaa", return"aaacecaaa".

Given"abcd", return"dcbabcd".

Solution 1: 3指针。找以第一个字母开头的最长palindrome，然后把剩下的substring reverse后接到头部

    public String shortestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] chars = s.toCharArray();
        int i = 0, end = chars.length - 1, j = end;
        while (i < j) {
            if (chars[i] == chars[j]) {
                i++;
                j--;
            } else {
                i = 0;
                end--;
                j = end;
            }
        }
        return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
    }

Solution 2: KMP

https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation