本文共203字,大约需要阅读1分钟。
代码如下:
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 36 37 38 39 40 41 42
| #include<bits/stdc++.h> using namespace std; int n,p[51000100],ans=1; char a[51000100],s[102000200]; void manacher() { int maxright=0,mid=0; for(int i=0;i<n;i++) { if(i<maxright) p[i]=min(p[2*mid-i],maxright-i); else p[i]=1; for(;i-p[i]>=0&&s[i+p[i]]==s[i-p[i]];p[i]++); if(p[i]+i>maxright) maxright=p[i]+i,mid=i; } } void change() { s[0]=s[1]='#'; for(int i=0;i<n;i++) { s[i*2+2]=a[i]; s[i*2+3]='#'; } n=n*2+2; s[n]=0; } int main() { scanf("%s",a); n=strlen(a); change(); manacher(); for(int i=0;i<n;i++) { ans=max(ans,p[i]); } printf("%d\n",ans-1); return 0; }
|


本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
当前页共有次阅读,条评论。
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏