首页 > 代码库 > 3160 最长公共子串
3160 最长公共子串
3160 最长公共子串
时间限制: 2 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。
输入描述 Input Description
读入两个字符串
输出描述 Output Description
输出最长公共子串的长度
样例输入 Sample Input
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother
样例输出 Sample Output
27
数据范围及提示 Data Size & Hint
单个字符串的长度不超过100000
分类标签 Tags 点此展开
后缀树 后缀树组 树结构
模板题：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=2e5+10;int n,c[N],h[N],sa[N],tsa[N],rank[N],trank[N];char s[N];struct Suffix{ void DA(int maxx=256){ int p; for(int i=0;i<=maxx;i++) c[i]=0; 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; for(int i=0;i<=maxx;i++) c[i]=0; 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 work(){ scanf("%s",s+1);n=strlen(s+1); s[++n]=‘#‘;int T=n; scanf("%s",s+n+1);int t=strlen(s+n+1); n+=t; DA(); //min(两个Suffix的lcp){Suffix不包含‘#‘} int ans(0); for(int i=1;i<=n;i++){ if(ans<h[i]){ if(sa[i]>T&&sa[i-1]<T) ans=h[i]; if(sa[i]<T&&sa[i-1]>T) ans=h[i]; } } printf("%d\n",ans); }}suffix;int main(){ suffix.work(); return 0;}
3160 最长公共子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。