最短回文串

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例1:

输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:

输入: "abcd"
输出: "dcbabcd"

主要思路：
本题是KMP算法的一种运用，利用Next数组解题法宝，利用KMP求解最长回文前缀
例如abc这个字符串，前缀加上cba，由于a一个字符可以看作是回文的，所以我们删除a，只用加上cb构成cbabc这个最短的回文字符串，再比如cbjbcb这个字符串，先反转得到bcbjbc，由于cbjbc本身就是回文的，反转后还是本身，所以这个删除两个字符串重叠的部分，得到bcbjbcb这个最短的回文子串
继续分析，其实我们就是求s的最长回文前缀，那么我们怎么求解这个最长回文前缀呢？
我们将s反转后s的前缀将会变成后缀，所以我们将s和s的反转字符串拼在一起，就是寻找这个新字符串的最长公共前后缀，然后return reverse删除公共部分+s原字符串即为答案
tips： 这里我们在拼接两个字符串时，加了一个‘#’号，如果不加，例如aaa这种情况，拼接后变成aaaaaa，利用KMP求得为6，其实最长回文前缀为3，可以有效防止此类特殊情况出现

public class ShortestPalindrome {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		String s = "aacecaaa";
		String res = shortestPalindrome(s);
		System.out.println(res);
	}
	public static String  shortestPalindrome(String s) {
		String reverse = "";
		int l = s.length()-1;
		for(int i = l;i>=0;i--) {
			reverse+=s.charAt(i);
		}
		String s1 = s+'#'+reverse;
		int max_len = getNext(s1);
		return reverse.substring(0, l-max_len)+s;
		
    }
	public static int getNext(String s) {
		int l = s.length();
		int i = 0;
		int j = -1;
		int [] next = new int[s.length()];
		next[0] = -1;
		
		while(i<l-1) {
			if(j==-1||s.charAt(i)==s.charAt(j)) {
				i++;
				j++;
				next[i] = j;
			}else
				j = next[j];
		}
		return next[l-1];		
	}

}