hdu_1403_Longest Common Substring(后缀数组的应用)

题目链接:hdu_1403_Longest Common Substring

题意:

给你两个字符串,然你找最长的公共子串

题解:

后缀数组的经典应用,要找两个字符串的公共子串,那么就相当于找两个串的后缀的最长公共前缀,我们将两个字符串拼接在一起,中间插一个特殊字符

然后我们考虑height数组,height数组存的是排i和i-1的最长前缀,如果sa[i]和sa[i-1]在特殊字符的两边,那么这个height[i]记录的就是这两个串的最长

子串,然后扫一遍height数组更新一下答案就行了

 #include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std; namespace suffixarray{
#define FN(n) for(int i=0;i<n;i++)
const int N =2E5+;//字符串长度
int rnk[N],sa[N],height[N],c[N];char s[N];
void getsa(int n,int m,int *x=rnk,int *y=height){
FN(m)c[i]=;FN(n)c[x[i]=s[i]]++;FN(m)c[i+]+=c[i];
for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;
for(int k=,p;p=,k<=n;k=p>=n?N:k<<,m=p){
for(int i=n-k;i<n;i++)y[p++]=i;
FN(n)if(sa[i]>=k)y[p++]=sa[i]-k;
FN(m)c[i]=;FN(n)c[x[y[i]]]++;FN(m)c[i+]+=c[i];
for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y),p=,x[sa[]]=;
for(int i=;i<n;i++)
x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;
}
FN(n)rnk[sa[i]]=i;
for(int i=,j,k=;i<n-;height[rnk[i++]]=k)
for(k=k?k-:k,j=sa[rnk[i]-];s[i+k]==s[j+k];k++);
}
}
using namespace suffixarray;
int main(){
while(~scanf("%s",s))
{
int len=strlen(s),sz;
s[len]='$';
scanf("%s",s+len+);
sz=strlen(s),getsa(sz+,);
int ans=;
F(i,,sz)if(ans<height[i]&&(sa[i]-len)*(sa[i-]-len)<)ans=height[i];
printf("%d\n",ans);
}
return ;
}
上一篇:框架Maven笔记系列 一 基础


下一篇:jquery.Huploadify 上传