网站建设杭州缘择低价/网络软文名词解释

/*3160 最长公共子串

给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。

读入两个字符串

输出最长公共子串的长度*/

//后缀数组的简单应用，求最长公共子串，先将两个子串连起来，求h数组中的最大值
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 2000005
using namespace std;
int a[N],sa[2][N],rk[2][N],v[N],n,k,mid,h[N],ans;
char ch[N];
void jin(int sa[N],int rk[N],int SA[N],int RK[N])
{for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;for(int i=n;i;i--)if(sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;for(int i=1;i<=n;i++)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);return;
}
int main()
{scanf("%s",ch+1);mid=strlen(ch+1);ch[++mid]='z'+1;scanf("%s",ch+mid+1);n=strlen(ch+1);int p=0,q=1;for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;for(int i=1;i<=n;i++)v[a[i]]++;for(int i=1;i<31;i++)v[i]+=v[i-1];for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;for(int i=1;i<=n;i++)rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);for(k=1;k<n;k<<=1,swap(p,q))jin(sa[p],rk[p],sa[q],rk[q]);k=0;for(int i=1;i<=n;i++)if(rk[p][i]==1)h[1]=0;else{int j=sa[p][rk[p][i]-1];for(;a[j+k]==a[i+k];k++);h[rk[p][i]]=k;if(k>0)k--;}for(int i=2;i<=n;i++)if((sa[p][i]>mid)^(sa[p][i-1]>mid))ans=max(ans,h[i]);printf("%d",ans);return 0;
}

转载于:https://www.cnblogs.com/xydddd/p/5153344.html