【无聊放个模板系列】HDU 3068 MANACHER

时间：2022-03-30 08:08:20
 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 110010

 char s[Maxn];

 int l;

 int a[Maxn*],al,p[Maxn*];

 int mymin(int x,int y) {return x<y?x:y;}

 int mymax(int x,int y) {return x>y?x:y;}

 void manacher()

 {

     int mx=,id=;

     for(int i=;i<=al;i++)

     {

         int k;

         if(i<mx) k=mymin(p[*id-i],mx-i+);

         else k=;

         while(a[i+k]==a[i-k]&&i-k>=&&i+k<=al) k++;

         p[i]=k;

         if(i+p[i]->mx) mx=i+p[i]-,id=i;

     }

 }

 int main()

 {

     while(scanf("%s",s+)!=EOF)

     {

         l=strlen(s+);

         al=;

         for(int i=;i<=l;i++) a[++al]=,a[++al]=s[i]-'a'+;

         a[++al]=;a[++al]=;

         manacher();

         int mx=;

         for(int i=;i<=al;i++) mx=mymax(mx,p[i]-);

         printf("%d\n",mx);

     }

     return ;

 }

马拉车

相关文章