首页 > 代码库 > hdu 4513 吉哥系列故事——完美队形II
hdu 4513 吉哥系列故事——完美队形II
參见hdu 3068 的manacher算法
代码例如以下:
#include<stdio.h> #include<string.h> #define M 110010 int s[M],ss[M*2];//s代表原来的字符串,ss代表插入之后的字符串 int p[M*2]; //表示以i为中心的(包括i这个字符)回文串半径长 int min(int a,int b) { return a>b?b:a; } int main() { int i,id,mx,max,t,x,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i]); ss[0]=‘$‘; for(i=0;i<n;i++) { ss[2*i+1]=‘#‘; ss[2*(i+1)]=s[i]; } ss[2*i+1]=‘#‘; ss[2*(i+1)]=‘\0‘; id=1; mx=0; max=0; for(i=1;i<2*n+2;i++) { if(mx>i) p[i]=min(mx-i,p[2*id-i]); else p[i]=1; while(ss[i+p[i]]==ss[i-p[i]]&&ss[i-p[i]]<=ss[i+2-p[i]]) { p[i]++; } if(i+p[i]>mx) { mx=i+p[i]; id=i; } if(p[i]>max) max=p[i]; } printf("%d\n",max-1); } return 0; }
hdu 4513 吉哥系列故事——完美队形II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。