manacher算法是一个时间复杂度为O(n)的求解最长回文串的算法。
那么直奔主题，这个算法原理是什么，代码怎么写？
例如输入字符串S=”abaaba”,普通的做法是求每个字符初始l=r=i,s[–l]==s[++r]能得到的最大的r-l。这种方法的时间复杂度是O(n^2)。
manacher算法会事先构造好一个字符串T=”#a#b#a#a#b#a#”,为了找到最长回文字符串，manacher的做法是在从T中的第i元素开始往字符串的两边进行扩展，例如T[i-d]到T[i+d]表示的是以T[i]为中心的回文字符串，你看到这个表示应该就能理解实际上回文字符串的长度是2*d.
为了找到最长的回文子串，那么必不可少的就是找出以每个字符为中心的最长回文子串，然后比较之后才能找出最长的。在这里我们使用数组P来保存以T中每个字符为中心的最长回文子串的半径（既长度的一半）。
通过查看数组P，找到其中最大的数字，我们可以马上看出最长的回文字符串是“aba”通过插入这#字符，我们可以一次性的处理当输入字符串为奇数或者偶数的情况，而不需要分情况讨论。
观察P数组，我们发现P数组是中心对称的，而且在子串“aba”总相应的P数组{1,3,1}也是对称的，这种对称的情况可是说是一种特例，但是他却能帮我们减少运算量。
举个更复杂的例子S=”babcbabcbaccba”.
上面的图片是从S转换之后得到的T,假设你已经完成了P数组的部分数值的计算，图中的实线表示当前回文串 “abcbabcba”的中心(center C )，两条虚线分别表示以C为中心的回文串的边界。你先需要计算的是 i 的值，图中i’表示的是i关于C 对称的点。那么问题来了，怎么计算更有效率的算出P[i]值。
假设当前i的值是13,我们需要得到P[13]的值,我们首先看下i关于C对称的i’=9的值。
两条绿色实线覆盖的区域分表表示的是以i’和i为中心的最长回文子串。我们已经知道了P[i’]=P[9]=1,那么非常明显,我们可以推断出P[i]=P[i’]=1, 因为回文子串的对称性。(这里稍微解释一下： 因为我们已经知道 a )
正如你在上一段看到的一样，P[i] = P[i’] = 1,这个是由回文子串关于其中心的对称性所决定的。实际上在C之后的三个元素都遵循了这种对称性（既 P[12] = P[10] = 0, P[13] = P[9] =1, P[14] = P[8] = 0 ).
现在我们到了 i = 15 这个点，i 关于 C对称的点是 i’ = 7 ,那么这里 P[15] = P[7] = 7 还会不会成立呢?
很不幸，这个时候如果认为P[15] 那就错了，如果我们以T[15] 为中心开始两边扩展，那么得到的最长回文子串是”a#b#c#b#a”, 这比我们根据对称性所得到的值 7 要小，那么原因是什么？
在上图中，绿色实线表示的是以C为中心的最长回文子串所覆盖的区域，红色实线表示的是与绿色区域不匹配的部分，左边的红色实线是以i’为中心的最长回文子串所覆盖区域超出绿色实线的部分。右边的红色实线是以i为中心的最长回文子串所覆盖区域超出绿色实线的部分。而绿色的虚线部分则是分别以 i 和 i’ 为中心最长回文子串与 绿色实线部分的重叠部分。
从图中我们可以明显的看出被两条绿色实线所覆盖的区域中，C两边的子串是完全相同的。同时绿色虚线的那部分也是关于中心对称的。但是需要注意的是 P[i’] = 7，此时以T[i’]为中心的最长回文子串超出了以C为中心的最长回文子串的左边界(图中L, 左边红色实线)，正是因为这个原因，这个时候无法再按照回文子串的对称性来处理了。
现在我们知道的是P[i]>=5 ,为了找出P[i]最终的值，我们只有继续以P[i]为中心向两边扩展进行比较，在这个例子中P[21]不等于P[1],那么我们最终推断是P[i]=5.
代码说明：
P[i]为s中第i个字符为中心的最长回文串的边界到中心的距离,i加上p[i],就是以i为中心的最长回文子串的右边界,用两个辅助变量分别是id,和mx。mx代表之前所有回文串最右右边界,id代表那最右右边界的下标。由于每次扩张都会导致mx变大，而mx最大不会超过strlen(s)，所以时间复杂度为O(n)。
