hdu3068 && Luogu 3805 manacher 模板
模板题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<cstdio> #include<cstring> #include<ctime> #include<queue> #define rep(i,x,y) for(register int i = x;i <= y;++i) #define repd(i,x,y) for(register int i = x;i >= y;--i) using namespace std; const int N = 22000111; char s[N]; int len,p[N]; int main() { while(~scanf("%s",s+1)) { len = strlen(s+1); repd(i,len,1) { s[i<<1] = s[i]; s[i<<1|1] = '#'; } s[1] = '#'; s[0] = '$'; int id = 0,maxp = 0,ans = 0; rep(i,1,2*len) { if(maxp > i) p[i] = min(maxp - i ,p[id*2 - i]); else p[i] = 1; while(s[i+p[i]] == s[i-p[i]]) ++p[i]; if(maxp < p[i] + i) maxp = p[i] + i,id = i; ans = max(ans,p[i] - 1); } printf("%d\n",ans); } return 0; } |