忘了具体什么时候写的，应该是 2023.8 初

这算是个算法复习，因为我太菜了以前学的都不会了。

manacher 回文串处理算法

其实这个我已经看两天了却一直没有看懂，觉得自己很愚笨，结果发现是自己一直不想去理解吧，然后今天仔细研究了以后发现就是那么个东西，没有什么很深奥的东西，那就自己整理一下思路吧。

manacher 算法的本质其实也是历史信息运用吧，我们观察到回文串都有个中心，奇数和偶数不一样，不过我们可以直接在每个字符之间加一个无用字符让它们都变成相对好处理的奇回文串。

• 如果一个串是回文串并且被另外一个回文串包含，那么它对称过去的串也是回文串。
  基本思路就是这个，但是这个算出来的回文串不一定最大，所以我们只需要暴力扩张即可。

均摊复杂度线性，我不会证明，但是看上去就挺线性的（）。

乱搞即可：

\(Code\)

int n,a[25000007],w[25000007],ans;//w表示回文半径（包括自己）
int main(){
    for(char c=getchar();c!=EOF;c=getchar())
        a[(n+=2)]=c-'a'+1;
    n++;a[0]=-1;//懒得特判了，让0不一样即可。
    for(int i=1,r=-1,mid=-1;i<=n;i++){
        if(i<=r)w[i]=min(w[(mid<<1)-i],r-i+1);
        while(a[i-w[i]]==a[i+w[i]])w[i]++;
        if(i+w[i]>r)r=i+w[i]-1,mid=i;
        // 因为包括了自己,所以要多减一个1
        if(w[i]>ans)ans=w[i];
    }
    cout<<ans-1;//半径就是答案，但是因为包括了自己，所以要减一
}