manacher

# manacher 求最长的回文子串。 ```cpp #include<bits/stdc++.h> #define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl #define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl using namespace std; const int maxn=1.1e7+100; bool cur1; int n; char str[maxn<<1]; int len[maxn<<1]; bool cur2; int main(){ // double Sz=&cur1-&cur2; // cout<<Sz/1024<<"KB "<<Sz/1024/1024<<"MB"<<endl<<endl; // freopen("data.in","r",stdin); // freopen("my.out","w",stdout); scanf("%s",str+1); n=strlen(str+1)*2+1; for(int i=n-1;i>=2;i-=2) str[i]=str[i>>1]; str[0]='$'; for(int i=1;i<=n;i+=2) str[i]='#'; int mid=0,right=0,mxlen=0; for(int i=1;i<=n;i++){ len[i]=(i<=right?min(len[2*mid-i],right-i+1):1); while(str[i+len[i]]==str[i-len[i]])len[i]++; if(i+len[i]>right)mid=i,right=i+len[i]-1; mxlen=max(mxlen,len[i]); } cout<<mxlen-1<<endl; return 0; } ``` 可以看出，本质不同的回文子串个数是$O(n)$级别的。 求回文子串个数只需要枚举中点即可