shortest palindrome

The fastest solution uses KMP algorithm. I find it's too hard. Another solution that is easier to understand is to search from the middle, if we reach the end of the left side of the string, then we only need to add left part of the right side (reverse) to the string. If we cannot find such a palindrome, we iteratively move the index to left until we find one.

public String shortestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int mid = (len - 1) / 2;
        String rst = null;
        for (int i = mid; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                if ((rst = getShortest(s, i, i + 1)) != null) {
                    break;
                }
            }
            if ((rst = getShortest(s, i, i)) != null) {
                break;
            }

        }
        return rst;
    }
    
    private String getShortest(String s, int l, int r) {
        int i = 1;
        while (l - i >= 0 && r + i < s.length() && s.charAt(l - i) == s.charAt(r + i)) {
            i++;
        }
        if (l - i >= 0) {
            return null;
        }
        String prefix = new StringBuilder(s.substring(r + i)).reverse().toString();
        return prefix + s;
    }

Here is the KMP solution.

public String shortestPalindrome(String s) {
        if (s == null || s.length() <= 1)
            return s;
        String reverse = new StringBuilder(s).reverse().toString();
        int longest = findPMT(s + "#" + reverse);
        return reverse.substring(0, reverse.length() - longest) + s;
    }

    private int findPMT(String ptrn) {
        int ptrnLen = ptrn.length();
        //partial match table
        int[] PMT = new int[ptrnLen + 1];
        PMT[0] = -1;
        PMT[1] = 0;
        for (int i = 2; i <= ptrnLen; i++) {
            int j = PMT[i - 1];
            while(j >= 0 && ptrn.charAt(j) != ptrn.charAt(i - 1)) {
                j = PMT[j];
            }
            PMT[i] = j < 0 ? 0 : j + 1;
        }
        return PMT[ptrnLen];
    }