1 条题解
-
0
马拉车板子。记得开两倍数组。
#include<iostream> #include<algorithm> #include<vector> #define int long long using namespace std; const int N=1e6+7; string str; char s[N]={0,'#'}; int d[N]; int cnt; signed main(){ while(cin>>str && str!="END"){ int n=str.size(),ans=0; str="#"+str; for(int i=1;i<=n;i++) s[i<<1]=str[i],s[i<<1|1]='#'; n=n<<1|1; for(int i=1;i<=n;i++) d[i]=0; int mid=0,dis=0; for(int i=1;i<=n;i++){ if(i<=mid+dis) d[i]=min(d[(mid<<1)-i],mid+dis-i); if(i+d[i]>=mid+dis){ while(i+d[i]+1<=n && i-d[i]-1>=1 && s[i+d[i]+1]==s[i-d[i]-1]) d[i]++; mid=i,dis=d[i]; ans=max(ans,dis); } } cout<<"Case "<<++cnt<<": "<<ans<<'\n'; } return 0; }
- 1
信息
- ID
- 608
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 9
- 已通过
- 3
- 上传者