主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
题解 CF432D 【Prefixes and Suffixes】
最后更新于 2025-06-15 21:08:37
作者
世末OIer
分类
题解
题解
CF432D
复制 Markdown
查看原文
更新内容
Z-function (因该首先想到的不是它吧) ```cpp #include<bits/stdc++.h> using namespace std; char s[111111]; int l,r,i,j,k,cnt,n,z[111111],ans[111111]; pair<int,int> res[111111]; int main(){ scanf("%s",s); n=strlen(s); l=0,r=0,z[0]=n; for(i=1;i<n;++i){ //计算出所有的z的值 if(i>r){ j=0; while(s[j]==s[i+j]) ++j; l=i,r=i+j-1,z[i]=j; }else{ k=i-l; if(z[k]<r-i+1) z[i]=z[k]; else{ j=r; while(s[j]==s[j-i]) ++j; l=i,r=j-1,z[i]=r-l+1; } } } for(i=0;i<n;++i) ++ans[z[i]]; //统计个数 for(i=n-1;i;--i) ans[i]+=ans[i+1]; for(i=0;i<n;++i) if(i+z[i]==n) res[++cnt]=make_pair(z[i],ans[z[i]]); sort(res+1,res+cnt+1); //按照要求排个序 printf("%d\n",cnt); for(i=1;i<=cnt;++i) printf("%d %d\n",res[i].first,res[i].second); return 0; } ```
正在渲染内容...
点赞
13
收藏
0
