https://leetcode.com/problems/shortest-palindrome/?tab=Description
在当前字符串前添加最短字符串，生成回文
暴力解法是找出前缀位置的最长回文
KMP做法，找当前String反转之后为revStr，求str + “&” + revStr的KMP的next数组。该next数组的最后一位表示包含当前位在内的前序位与str前缀相同的长度。因为是revStr是翻转过的，因此next[len - 1]的长度也就是str前缀回文的最大长度。
public class Solution { public String shortestPalindrome(String s) { String temp = s + "*" + new StringBuilder(s).reverse().toString(); int[] next = getNext(temp); return new StringBuilder(s.substring(next[temp.length()])).reverse().toString() + s; } private int[] getNext(String s) { int[] next = new int[s.length() + 1]; for (int i = 1, j = 0; i < s.length(); i++) { while (j > 0 && s.charAt(i) != s.charAt(j)) { j = next[j]; } if (s.charAt(i) == s.charAt(j)) { j++; } next[i + 1] = j; } return next; } }