原题链接：https://leetcode-cn.com/problems/shortest-palindrome/
题目描述：
解法一：暴力搜索
寻找开头开始的最长回文串，
将原始字符串逆序，然后比较对应的子串即可判断是否是回文串。举个例子。
abbacd
原s: abbacd, 长度记为 n 逆r: dcabba, 长度记为 n
判断 s[0,n) 和 r[0,n) abbacd != dcabba
判断 s[0,n - 1) 和 r[1,n) abbac != cabba
判断 s[0,n - 2) 和 r[2,n) abba == abba
从开头开始的最长回文串也就找到了, 接下来只需要使用之前的方法。 将末尾不是回文串的部分倒置加到原字符串开头即可。
代码：
class Solution {
public String shortestPalindrome(String s) {
String rev = new StringBuffer(s).reverse().toString();
int n = s.length();
int i = 0;
//dcba abcd
for(i=0;i<n;i++)
{
if(s.substring(0,n-i).equals(rev.substring(i,n)))
break;
}
return new StringBuffer(s.substring(n-i)).reverse().toString()+s;
}
}
解法二：kmp算法求解
如果熟悉了 KMP 算法，就非常简单了。
再回想一下解法一，倒置字符串的思路，依次比较对应子串。
abbacd
原s: abbacd, 长度记为 n 逆r: dcabba, 长度记为 n
我们把两个字符串写在一起 abbacd dcabba
判断 abbacd 和 dcabba 是否相等
判断 abbac 和 cabba 是否相等
判断 abba 和 abba 是否相等
如果我们把 abbacd dcabba看成一个字符串，中间加上一个分隔符 #，abbacd#dcabba。
回味一下上边的三条判断，判断 XXX 和 XXX 是否相等，按列看一下。
左半部分 abbacd，abbac , abba 其实就是 abbacd#dcabba 的一些前缀。
右半部分dcabba，cabba，abba 其实就是 abbacd#dcabba 的一些后缀。
寻找前缀和后缀相等。
想一想 KMP 算法，这不就是 next 数组做的事情吗。
而我们中间加了分隔符，也就保证了前缀和后缀相等时，前缀一定在 abbacd 中。
换句话说，我们如果求出了 abbacd#dcabba 的 next 数组，因为我们构造的字符串后缀就是原字符串的倒置，前缀后缀相等时，也就意味着当前前缀是一个回文串，而 next 数组是寻求最长的前缀，我们也就找到了开头开始的最长回文串。
因为 next 数组的含义并不统一，但 KMP 算法本质上都是一样的，所以下边的代码仅供参考。
class Solution {
public String shortestPalindrome(String s) {
//kmp算法求解
//例如abbacd
//构造abbacd#dcabba
String temp = s+'#'+new StringBuffer(s).reverse().toString();
int result = getNext(temp);
return new StringBuffer(s.substring(result+1)).reverse()+s;
}
//返回next数组的最后一个值 返回的是3
public int getNext(String s)
{
char a[] = s.toCharArray();
int []next = new int[a.length];
next[0] = -1;
int i = -1;
int j = 0;
while(j<a.length-1)
{
if(i==-1 || a[i]==a[j])
{
i++;j++;
next[j] = i;
}
else
i = next[i];
}
return next[a.length-1];
}
}