题目：最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路和简单分析： 这道题刚开始没啥思路，本来打算暴力膜一波，但是感觉肯定无法通过... 看了网上很多解法都用了Manacher算法，能够在O(n)的情况找出最长的回文子串，虽然还看得不是很明白，但是跟着大概的思路能够AC，以后如果有时间会对代码做出优化。
思路比较简单，只需要遍历一遍数组，记录它能够组成回文字符串的半径，记录在数组p中。使用Manacher算法的思路避免奇数长和偶数长字符串的不同逻辑处理，使用不会在字符串中出现的字符做为分隔符对字符数组扩容。
上代码：
public String longestPalindrome(String s) {
char[] c = s.toCharArray();
//分隔字符
StringBuffer sb = new StringBuffer();
sb.append("#");
for (int i = 0;i<c.length;i++){
sb.append(c[i]);
sb.append("#");
}
int[] p = new int[sb.length()];
int max = 0;
int id = 0;
//计算回文串长度
for(int i = 0;i<sb.length();i++){
int count = 1;
p[i] = 1;
while (i-count>=0 && i+count<sb.length() && sb.charAt(i-count)==sb.charAt(i+count)){
p[i]++;
count++;
}
if(p[i]>max){
max = p[i];
id = i;
}
}
int r = max-1;
int start = id-r;
int end = id+r;
StringBuffer res = new StringBuffer();
//拼接最长回文串
for (int i = start;i<=end;i++){
if (sb.charAt(i)!='#'){
res.append(sb.charAt(i));
}
}
return res.toString();
}
}
