Manacher(马拉车算法)
Posted at 2024-12-02 ACM
本文共365字,阅读需要约1分钟
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; #define INT 22000007 char c[INT];//拓展后的偶字符串 int p[INT];//拓展得到的回文串长度 int manacher_init(char* s,char* c){ int l=strlen(s); int cnt=0; c[++cnt]='~'; c[++cnt]='#'; for (int i = 0; i < l; ++i) { c[++cnt]=s[i]; c[++cnt]='#'; } c[++cnt]='!'; return cnt; }//拓展来省去奇偶讨论 int manacher(char* s){ int cnt=manacher_init(s,c); int mid=0,mr=0,ans=0; for (int i = 2; i < cnt; ++i) { if(i<=mr)p[i]=min(p[mid*2-i],mr-i+1); else p[i]=1; while(c[i-p[i]]==c[i+p[i]]){ p[i]++; } if(i+p[i]>mr){ mr=i+p[i]-1; mid=i; } ans=max(ans,p[i]); } return ans-1; } int main(){ char s[1300]; while(scanf("%s",s)!=EOF){ cout<<manacher(s); } }
Previous post: KMP与拓展KMP Next post: Floyd