真的很烦有些人，想写博客么，又不好好写，最起码自己好好看一遍，纠纠错，写写感悟，只顾自己看懂而不加以探讨，那你写博客还有什么意义呢？更何况，看不看的懂还两说，接下来就为大家解释一下网上各种搜索排名靠前的关于O(n)时间求字符串的最长回文子串的算法，也就是Manacher's Algorithm。说真的，大部分解释真的很难看懂他们到底在说些什么。
大家都知道，求回文串时需要判断其奇偶性，也就是求aba 和abba 的算法略有差距。然而，这个算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘#’或者‘$’等字符。例如：
原串：abaab 新串：#a#b#a#a#b#这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心奇数回文串了。 接下来就是算法的中心思想，用一个辅助数组Radius[ ]，记录以每个字符为中心的最长回文半径，也就是R[i]记录以Str[i]字符为中心的最长回文串半径。R[i]最小为1，此时回文串为Str[i]本身。 我们可以对上述例子写出其R数组，如下 新串： # a # b # a # a # b # R[] : 1 2 1 4 1 2 5 2 1 2 1 我们可以证明R[i]-1 就是以Str[i]为中心的回文串在原串当中的长度。 证明： 1、显然L=2*R[i]-1 即为新串中以Str[i]为中心最长回文串长度。2、以Str[i]为中心的回文串一定是以#开头和结尾的，例如“#b#b#”或“#b#a#b#”所以L 减去最前或者最后的‘#’字符就是原串中长度的二倍，即原串长度为(L-1)/2，化简的R[i]-1。依次从前往后求得R数组就可以了，这里用到了DP(动态规划)的思想, 也就是求R[i] 的时候，前面的R[]值已经得到了，我们利用回文串的特殊性质可以进行一个大大的优化。
敲黑板，划重点！下面是该算法的核心思想。
如何去求这个R数组，是求解这道题的关键。我们使用两个辅助变量 id 和 mx ，其中 id 为已知的最长的回文子串的中心位置，那么 mx 则为 id + R[id]，也就是这个子串的右边界。
然后当你用变量 i 依次循环的时候，会有以下结论：
如果mx > i，那么R[i] >= MIN(R[2 * id - i], mx - i)
也就是说：
//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))if (mx - i > R[j]) R[i] = R[j];else /* R[j] >= mx - i */ R[i] = mx - i; // R[i] >= mx - i，取最小值，之后再匹配更新。
一图胜千言吧，看图说话：
当 mx - i > R[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 R[i] = R[j]，见下图。
当 R[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 R[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
基于以上思路，奉出JAVA代码
public class LongestPalindrome { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ String s = scanner.next(); System.out.println(CalPalindrome(BuildStr(s))); } } public static char[] BuildStr(String s){ StringBuilder sb = new StringBuilder(s); char[] ch = new char[2*s.length()+1]; for (int i = 1; i <= ch.length; i++) { if(i%2==0) ch[i-1] = sb.charAt(i/2-1); else ch[i-1] = '#'; } return ch; } public static int CalPalindrome(char[] ch){ int mx = 0; int id = 0; int[] R = new int[ch.length]; for (int i = 0; i < R.length; i++) { R[i] = 1;//因为数组中最小的值也是1，先初始化一下 } for (int i = 1; i < ch.length; i++) { R[i] = mx>i?Math.min(R[2*id-i], mx-i):1; while(i-R[i]>=0 && i+R[i] mx){ mx = i+R[i]; id = i; } } Arrays.sort(R); return R[R.length-1]-1; }}