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;
}