Manacher 算法

模板算法题

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5;
char s[M<<1];
int p[M<<1];
int main(){
  cin>>(s+1);
  int n=strlen(s+1);
  for(int i=2*n+1;i>=1;i--){  //初始化
    s[i]=(i&1)? '#':s[i>>1];
  }
  s[0]='^'; s[2*n+2]='$';
  int c=0; int r=0;
  for(int i=1;i<=2*n+1;i++){
    p[i]=(i<r)?min(p[2*c-i],r-i):1;  //min防止越界
    while(s[i+p[i]]==s[i-p[i]]) p[i]++;  //向两边扩大
    if(i+p[i]>r){    //更新更优情况
      c=i; r=i+p[i];
    } 
  }
  int ans=-1;
  for(int i=1;i<=2*n+1;i++){
    ans=max(ans,p[i]-1);  //p[i]-->回文半径   p[i]-1-->回文子串长度
  }
  cout<<ans<<'\n';
  return 0;
}