HiHo 1032 最长回文子串 (Manacher算法求解)

Manacher算法o(n)求解最长回文子串问题 非常巧妙

#include
  
   
using namespace std;
char str[2000020],s[2000020];
int p[2000020];
int len,id,mx;
void pre() //对字符串进行预处理
{
    len=strlen(s);
    str[0]='$';
    str[1]='#';
    for(int i=0;i
   
    i) p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(str[i+p[i]]==str[i-p[i]]) p[i]++; if(p[i]+i>mx) { mx=p[i]+i; id=i; } } } int main() { int N; scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%s",s); pre(); Manacher(); printf("%d\n",p[max_element(p,p+len)-p]-1); } return 0; }