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".

一刷
题解：
我们首先构造s.reverse() + "#" + s的KMP look up table
然后得到table中最后一个元素的值则是需要剔除掉部分。
例如“abc”, [0,0, 1], 除去a, reverse() + s: "cbabc"

public class Solution {
    public String shortestPalindrome(String s) {
        String temp = s + "#" + new StringBuilder(s).reverse().toString();
        int[] table = getTable(temp);
        
        return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
    }
    
    private int[] getTable(String s){
        //get lookup table
        int[] table = new int[s.length()];
        
        //pointer that points to matched char in prefix part
        int index = 0;
        //skip index 0, we will not mach a string with itself
        for(int i=1; i<s.length(); i++){
            if(s.charAt(index) == s.charAt(i)){
                //we can extend match in prefix and postfix 
                table[i] = table[i-1] + 1;
                index++;
            }else{
            //match failed, we try to match a shorter substring
            
            //by assigning index to table[i-1], we will shorten the match string length, and jump to the 
            //prefix part that we used to match postfix ended at i - 1
                
                index = table[i-1];
                
                while(index>0 && s.charAt(index)!=s.charAt(i)){
            //we will try to shorten the match string length until we revert to the beginning of match (index 1)
                    index = table[index-1];
                }
                
                 //when we are here may either found a match char or we reach the boundary and still no luck
                //so we need check char match
                if(s.charAt(index) == s.charAt(i)) {
                     //if match, then extend one char 
                    index++;
                }
                
                table[i] = index;
            }
        }
        
        return table;
    }
}

二刷
思路同上，但是KMP算法写得还是不熟练。