Manacher

给定一个字符串，求它的最长回文子串的长度。

这里要注意，回文串是要分奇回文串和偶回文串。为了避免讨论，我们在字符中间加入特殊字符。如\(abaabbc\)变为#\(a\)#\(b\)#\(a\)#\(a\)#\(b\)#\(b\)#\(c\)#。

时间复杂度为\(O(n)\)。

\(code\)：

void change()
{
    for(int i=len;i;--i)  s[i<<1]=s[i];
    for(int i=1;i<=(len<<1)+1;i+=2) s[i]='#';
    len=(len<<1)+1;
}
void manacher()
{
    int mid=1;
    for(int i=1;i<=len;++i)
    {
        sum[i]=min(sum[(mid<<1)-i],sum[mid]+mid-i);
        while(i+sum[i]<=len&&i-sum[i]>=1&&s[i+sum[i]]==s[i-sum[i]])
            sum[i]++;
        if(sum[i]+i>sum[mid]+mid) mid=i;
    }
}

......

len=strlen(s+1);
change();
manacher();
ans=1;
for(int i=1;i<=len;++i)
    ans=max(ans,sum[i]-1);//注意要-1

Manacher

原文：https://www.cnblogs.com/lhm-/p/12229443.html