首页 > 代码库 > CSU-1632 Repeated Substrings[后缀数组求重复出现的子串数目]
CSU-1632 Repeated Substrings[后缀数组求重复出现的子串数目]
评测地址：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+5;int T,n,ans,c[N],sa[N],tsa[N],trank[N],rank[N],h[N];char s[N];void DA(int maxx=256){ memset(c,0,sizeof c);int p; for(int i=1;i<=n;i++) c[rank[i]=s[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=n;i;i--) sa[c[rank[i]]--]=i; trank[sa[1]]=p=1; for(int i=2;i<=n;i++){ if(rank[sa[i]]!=rank[sa[i-1]]) p++; trank[sa[i]]=p; } for(int i=1;i<=n;i++) rank[i]=trank[i]; for(int k=1;p<n;k<<=1,maxx=p){ p=0; for(int i=n-k+1;i<=n;i++) tsa[++p]=i; for(int i=1;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k; memset(c,0,sizeof c); for(int i=1;i<=n;i++) trank[i]=rank[tsa[i]]; for(int i=1;i<=n;i++) c[trank[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i]; trank[sa[1]]=p=1; for(int i=2;i<=n;i++){ if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++; trank[sa[i]]=p; } for(int i=1;i<=n;i++) rank[i]=trank[i]; } for(int i=1,k=0;i<=n;i++){ int j=sa[rank[i]-1]; while(s[i+k]==s[j+k]) k++; h[rank[i]]=k;if(k>0)k--; }}void GO(){ ans=0; for(int i=1;i<=n;i++) if(h[i]>h[i-1]) ans+=h[i]-h[i-1]; printf("%d\n",ans);}int main(){ scanf("%d",&T); while(T--){ scanf("%s",s+1);n=strlen(s+1); DA(); GO(); } return 0;}
CSU-1632 Repeated Substrings[后缀数组求重复出现的子串数目]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。