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;

}