CSU-1632 Repeated Substrings[后缀数组求重复出现的子串数目]
2024-09-03 21:34:05
评测地址:https://cn.vjudge.net/problem/CSU-1632
Description
求字符串中所有出现至少2次的子串个数
Input
第一行为一整数T(T<=10)表示用例组数,每组用例占一行为一个长度不超过100000的字符串
Output
对于每组用例,输出该串中所有出现至少两次的子串个数
Sample Input
3
aabaab
aaaaa
AaAaA
Sample Output
5
4
5
Solution
Ans=sum(max(height(i)-height(i-1),0))
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+;
int T,n,ans,c[N],sa[N],tsa[N],trank[N],rank[N],h[N];
char s[N];
void DA(int maxx=){
memset(c,,sizeof c);int p;
for(int i=;i<=n;i++) c[rank[i]=s[i]]++;
for(int i=;i<=maxx;i++) c[i]+=c[i-];
for(int i=n;i;i--) sa[c[rank[i]]--]=i;
trank[sa[]]=p=;
for(int i=;i<=n;i++){
if(rank[sa[i]]!=rank[sa[i-]]) p++;
trank[sa[i]]=p;
}
for(int i=;i<=n;i++) rank[i]=trank[i];
for(int k=;p<n;k<<=,maxx=p){
p=;
for(int i=n-k+;i<=n;i++) tsa[++p]=i;
for(int i=;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;
memset(c,,sizeof c);
for(int i=;i<=n;i++) trank[i]=rank[tsa[i]];
for(int i=;i<=n;i++) c[trank[i]]++;
for(int i=;i<=maxx;i++) c[i]+=c[i-];
for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i];
trank[sa[]]=p=;
for(int i=;i<=n;i++){
if(rank[sa[i]]!=rank[sa[i-]]||rank[sa[i]+k]!=rank[sa[i-]+k]) p++;
trank[sa[i]]=p;
}
for(int i=;i<=n;i++) rank[i]=trank[i];
}
for(int i=,k=;i<=n;i++){
int j=sa[rank[i]-];
while(s[i+k]==s[j+k]) k++;
h[rank[i]]=k;if(k>)k--;
}
}
void GO(){
ans=;
for(int i=;i<=n;i++) if(h[i]>h[i-]) ans+=h[i]-h[i-];
printf("%d\n",ans);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+);n=strlen(s+);
DA();
GO();
}
return ;
}
最新文章
- 【完整靠谱版】结合公司项目,仔细总结自己使用百度编辑器实现FTP上传的完整过程
- eclipse左侧不见
- oracle 11g dmp文件导入10g
- 个人制作-css+html旋转立方体的制作
- tornado 反向代理后 获取真实客户端IP
- C++ --- Hellowrod
- 【Agorithm】一次一密加密解密算法
- Gym 100463D Evil DFS
- 哈哈,好像swift 以后有可能用来开发安卓喔
- 关于两个php.ini的说明
- Java拾穗
- Quartz.net一个简要示例
- SaaS应用“正益工作”发布,为大中型企业轻松构建移动门户
- Android 之 资源文件的介绍及使用
- Android学习笔记——Activity的启动和创建
- Domain=com.alamofire.error.serialization.response Code=-1016 ";Request failed: unacceptable content-type: text/html";
- 【BZOJ1500】【Noi2005】维修数列
- Android简易实战教程--第二十四话《画画板》
- mysql关联表更改表多个字段值
- AngularJS学习之旅—AngularJS 模块(十五)
热门文章
- UGUI 实现界面 渐隐渐现 FadeIn/Out 效果
- windows 7 提示升级到windows 10补丁
- What most young programmers need to learn
- atitit.MyEclipse10 中添加svn插件故障排除
- URL中的#号
- Android学习笔记(一)——Activity简介 和 View
- node-webkit中使用sqlite3
- Silverlight实例教程 - Validation数据验证DataAnnotation机制和调试技巧(转载)
- FPGA研发之道(25)-管脚
- objc_setAssociatedObject 使用(转)