并不对劲的manacher算法

有些时候，后缀自动机并不能解决某些问题，或者解决很麻烦。这时就有各种神奇的字符串算法了。

manacher算法用来O(|S|)地求出字符串S的最长的回文串的长度。这是怎么做到的呢？

并不对劲的暴力选手在刚见到求字符串S的最长的回文串的长度这个问题时，第一反应就是枚举每一个位置为回文串的对称轴，再暴力地判断。由于回文串的对称轴可能在缝隙处，对于奇偶还要特判。这时最好每隔一个字符插入一个奇怪的字符。对暴力做一些优化，就是用二分+哈希来判断。不过这也只能o(|S| log²|S|)地做出来。能不能利用回文串的某些性质呢？

设r[i]表示以i为对称轴，是S[i+1]与S[i-1]，S[i+2]与S[i-2]，…，S[i+x]与S[i-x]，相等的最大的x。定义s(i,r[i])表示以i为对称轴的且右端点为i+r[i]的回文串。

那么i-r[i]到i+r[i]这一段就是对称的。

记已算出的最大的i+r[i]为maxr （也就是已算出的回文串的右端点中最靠右的），maxr的i为maxi。

若要算出r[a]，则：

若a>=maxr，直接按定义暴力地求出r[a]。

若a<maxr，则先找出a关于maxi的对称点b。则r[a]>=min(r[b],maxr-a)。

 当r[b]<maxr-a时,a+r[b]<maxr，所以s(b,r[b])肯定被s(maxi,maxr)包含。由于a与b关于maxi对称，所以以a为对称轴的回文串中，肯定有一个等于ls(b,r[b])。又因为r[b]是b的最长回文子串的右端点，所以S[b-r[b]-1]!=S[b+r[b]+1]，根据对称性又能推出S[a-r[b]-1]!=S[a+r[b]+1]。所以此时r[a]=r[b]。

当r[b]>=maxr-a时，b-r[b]<maxi-r[maxi]，也就是说，s(b,r[b])中有一部分在s(maxi,maxr)外，不符合对称性。这一部分是不能算的。所以此时r[a]>=min(r[b],maxr-a) 

这样先令r[a]=min(r[b],maxr-i)，剩下的按定义暴力求就行了。

字符串S的最长的回文串的长度就是最大的r[i]了。这是因为如果算上奇怪的字符，那么r[i]对应的回文串长度是r[i]*2+1。修改后的字符串每隔一个字符就有一个奇怪的字符。这些奇怪的字符都相同，所以r[i]对应回文串的第一个字符和最后一个字符都是奇怪的字符（形如#a#b#a#或#a#a#）。那么不是奇怪的字符一共有(r[i]*2+1-1)/2=r[i]个。

至于时间复杂度，并不对劲的人并不想不证明。因为每次有意义的比较都是maxr之后的部分，比较过的部分又会更新maxr。总的来看就是maxr将整个字符串扫了一遍，时间复杂度是O(|S|)，而且很好写。

不太清楚它能出成什么题？

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define maxn 11000010
using namespace std;
char s1[maxn],s2[maxn*2];
int n,mr,mid,r[maxn*2],ans;
int check(int x,int y)
{
    while(s2[x-y]==s2[x+y])y++;
    return y-1;
}
int main()
{
    scanf("%s",s1+1);
    n=strlen(s1+1);
    s2[0]=‘B‘,s2[n*2+2]=‘C‘; 
    for(int i=1;i<=n*2+1;i++)
    {
        if(i&1)s2[i]=‘A‘;
        else s2[i]=s1[i/2];
    }n=n*2+2;
    mr=mid=0;
    for(int i=1;i<=n;i++)
    {
        if(i>=mr)
            r[i]=check(i,1);
        else
            r[i]=check(i,min(r[mid*2-i],mr-i));
        if(r[ans]<r[i])
            ans=i;
        if(i+r[i]>mr){mid=i;mr=i+r[i];}
    }
    printf("%d",r[ans]);
    return 0;
}
//Shing has healthy hands.

并不对劲的manacher