Manacher法

首先，为了统一计算回文串遇到的长度为奇为偶的情况，因此在回文串的字符与字符之间加一个'#'，首位赋'$'，末位赋'\0'。因此我们要求的回文串长度均是奇数。

考虑对每一位（从角标1开始），算他们的回文串半径。

正常的思路是:

p[i]=1;

while(s[i-p[i]]==s(s[i+p[i]]))

p[i]++;

但是别忘了，我们已经在字符与字符之间加了一个'#',所以回文串长度应该和算出的回文半径有某种关系！实际上呢，回文半径-1=回文串长度。现在的工作就是降复杂度：一个好的想法就是利用已经有的信息。当我们算到p[i]的时候，前面i-1个已经算过了。那么现在就是找可利用的信息。假设现在已知一个id（id<i）,p[id],那么当i<p[id]即i落在id所占有的回文区域内时，我们是否可以利用i关于id的对称点j呢。j也在id的回文区域内，但是我们已知因为j<id，所以p[j]已知。

if(i<p[id]+id)

p[i]=min(p[id]+id-i,p[j]);

为什么是取最小值呢，分类讨论一下。我们可以假设，

1.j的回文区域并不完全落在id的回文区域内，那么，根据id的回文区域的对称性可得，i的回文半径至少是j-(id-p[id])也就等于是p[id]+id-i。可是我们先假设实际情况下i的回文半径比上述结果多1，那么问题来了，由回文的对称性可知（此处设mx=p[id]+id,lx=p[id]-id），mx+1和lx-1位置上的元素相等，由于他俩对id成对称分布，那么p[id]的结果就比实际结果少了1，矛盾，所以i的回文半径在这种情况下就是mx-1。

2.j的回文区域完全落在id回文区域内，那么，如果i的回文半径比j的还大，那么根据对称性，j的回文半径也要增大，可是j的回文半径已经算出，所以，i的回文半径就是j的回文半径！