SHortestPalindrome

gistfile1.java

/*
  kmp like method.
  1. build string  s + "#" + (reversed s)
  2. generate array of length of common prefix and suffix (like building next[] in kmp)
  3. append (reversed s).substring(0, length - next[-1] - 1)) in front of s   (Note: next[-1] - 1 is the length of max length on common prefix suffix at last position)
*/

public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        String rev = new StringBuilder(s).reverse().toString();
        String ss = s + "#" + rev;
        
        int[] next = genNext(ss);
        return rev.substring(0, rev.length() - next[next.length - 1] - 1) + s;
    }
    
    private int[] genNext(String p) {
        int[] next = new int[p.length()];
        next[0] = -1;
        int k = -1, j = 0;
        
        while (j < p.length() - 1) {
            if (k == -1 || p.charAt(j) == p.charAt(k)) {
                k++; j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }