Manacher算法是个解决Palindrome问题的O(n)算法，能够说是个超级算法了，秒杀其它一切Palindrome解决方式，包含复杂的后缀数组。
网上非常多解释，最好的解析文章当然是Leetcode的了：http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
这里总结一下思想重点：
1 原字符串的字符间插入新的字符， 如#，方便统一全部的字符中心，比方aa和aba的字符中心不一样的，aa的字符中心能够说是aa，而aba的中心则是b，而插入#之后，aa成#a#a#，当中心是一个字符#，而aba插入#a#b#a#，中心还是一个字符b。
2 充分利用前面已经计算出的信息来计算后面的信息，这里主要利用palindrome的对称性的特性，那么就能够利用对称中心前半段的信息计算后半段的信息了。这个是优化算法到O(n)的关键。 由于对称中心是不断右移的，故此在对称中心内的求解仅仅需直接copy前半段的信息就能够，而超出当前对称范围的就须要expand Palindrome了。
3 防止溢出，前面加一个额外的特殊字符，如'~'，和前面的插入字符不一样。后面也须要插入字符，可是为什么非常多程序不插入字符呢？那是由于C++的char都是以'\0'结束的，故此，不插入也是能够的，以下程序明显插入'\0'到结尾了。
4 须要维护最右点信息，中心信息和P数组，P数组的含义是以i点为中心的最长palindrome子字符串的长度，这里是长度+1，方便计算。
关键代码就几行，可是思想却是十分难的。
#include <stdio.h>
#include <string.h>const int MAX_2L = 220010;
char txt[MAX_2L];
int P[MAX_2L];
int len;
inline int min(int a, int b) { return a < b? a : b; }
inline int max(int a, int b) { return a > b? a : b; }void preProcess()
{len = strlen(txt);int i = len-1, j = (len<<1);txt[j+2] = '\0';txt[j+1] = '#';for ( ; i >= 0; i--){txt[j--] = txt[i];txt[j--] = '#';}txt[0] = '~';
}int main()
{while (gets(txt)){preProcess();len = len << 1 | 1;int maxLen = 0, right = 0, center = 0;for (int i = 1; i <= len; i++){P[i] = i<right ? min(P[(center<<1)-i], right-i) : 1;while (txt[i-P[i]] == txt[i+P[i]]) P[i]++;maxLen = max(maxLen, P[i]);if (right < i+P[i]) center = i, right = i+P[i];}printf("%d\n", maxLen-1);gets(txt); //get rid of empty line}return 0;
}