manacher算法

模板题：洛谷p3805

code:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2.2e7+10;
string t,s;
int m,n;
int d[N];
int main(){cin>>t;m=t.size();s+=' ';for(auto ch: t){s+='#';s+=ch;}s+="##";n=s.size()-2;d[1]=1;int ret=1;for(int i=2,l=1,r=1;i<=n;i++){int len=r>=i?min(d[r-i+l],r-i+1):1;while(s[i+len]==s[i-len])len++;if(i+len-1>r){r=i+len-1;l=i-len+1;}d[i]=len;ret=max(ret,d[i]-1);}cout<<ret<<endl;return 0;
}