Manacher
概述
Manacher 算法在线性时间内求出字符串每个位置的最长回文半径，进而得到最长回文子串。它在每两个字符间插入分隔符，把奇回文与偶回文统一成奇回文来处理；再维护当前右端最靠右的回文区间，用对称位置已算出的半径复用信息，避免从头重复扩展，从而把朴素的平方级做法降到线性。实现给出插入哨兵与分隔符、递推回文半径数组的完整函数。
参考资料
简介
Manacher 算法 在 内求出字符串每个位置的最长回文半径，从而得到最长回文子串。它在每两个字符间插入分隔符，把奇、偶回文统一成奇回文；再维护当前右端最靠右的回文区间 ，用对称位置已算出的半径复用信息，避免重复扩展。
实现
int p[N<<1];
int manacher(string s)
{
int n=s.size();
string t="@#";
for(int i=0;i<n;i++)
{
t+=s[i];
t+='#';
}
t+='&';
s=t;
n=n<<1|1;
for(int i=1,l=0,r=0;i<=n;i++)
{
p[i]=i<=r?min(p[2*l-i],r-i+1):1;
while(s[i-p[i]]==s[i+p[i]])p[i]++;
if(i+p[i]-1>r)r=i+p[i]-1,l=i;
}
return n;
}