[HDOJ1403 Longest Common Substring]【后缀数组】

【题目大意】求两个串的最长公共前缀。
【算法分析】
后缀数组，利用height数组高一下即可。会后缀数组的都会本题。。。
【其它】
1Y。
以前基数排序用邻接表写的，现在换了线性数组写。
另外也算省赛前对后缀数组的一个小复习吧。
【CODE】
#include #include #include const int N=205555;
const int LL=sizeof(int)*3;
int n,cut;
char str[N],s1[N],s2[N];
int sa[N],rank[N],Sum[N],a[N][3],b[N][3],height[N];

void Sort(){
for (int i,k=1;k>=0;k–){
for (i=0;i<=n;i++) Sum[i]=0;
for (i=1;i<=n;i++) Sum[a[i][k]+1]++;
for (i=1;i<=n;i++) Sum[i]+=Sum[i-1];
for (i=1;i<=n;i++) memcpy(&b[++Sum[a[i][k]]],&a[i],LL);
memcpy(&a[1],&b[1],LL*n);
}
}

void make_suffix_arr(){
int i,cnt=0,k,s;
for (i=0;i<256;i++) Sum[i]=0;
for (i=1;i<=n;i++) Sum[str[i]]++;
for (i=0;i<256;i++)
if (Sum[i])
Sum[i]=++cnt;
for (i=1;i<=n;i++) rank[i]=Sum[str[i]];
for (k=1;1< s=1<<(k-1);
for (i=1;i<=n;i++){
a[i][0]=rank[i];
if (i+s<=n) a[i][1]=rank[i+s];
else a[i][1]=0;
a[i][2]=i;
}
Sort();
for (cnt=0,i=1;i<=n;rank[a[i][2]]=cnt,i++)
cnt+=(!cnt || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]);
}
for (i=1;i<=n;i++) sa[rank[i]]=i;
}

inline int max(int x,int y){return x>y?x:y;}

void make_height(){
int i,j,k,st;
for (i=1;i<=n;i++){
if (rank[i]==1) continue;
st=max(0,height[rank[i-1]]-1);
j=i+st; k=sa[rank[i]-1]+st;
while (j<=n && k<=n && str[j]==str[k]){j++; k++; st++;}
height[rank[i]]=st;
}
}

void reply(){
int ans=0;
for (int i=3;i<=n;i++)
if ((sa[i-1] || (sa[i-1]>cut && sa[i] ans=max(ans,height[i]);
printf("%dn",ans);
}

int main(){
int L1,L2;
while (scanf("%s%s",s1+1,s2+1)!=EOF){
n=0;
L1=strlen(s1+1);
L2=strlen(s2+1);
memcpy(str+1,s1+1,sizeof(char)*L1);
str[L1+1]=’.’;
cut=L1+1;
memcpy(str+L1+2,s2+1,sizeof(char)*L2);
n=L1+L2+1;
make_suffix_arr();
make_height();
reply();
}
}