poj2774 Long Long Message 后缀数组求最长公共子串
题目链接：http://poj.org/problem?id=2774
这是一道很好的后缀数组的入门题目
题意：给你两个字符串，然后求这两个的字符串的最长连续的公共子串
一般用后缀数组解决的两个字符串的问题都通过将一个字符串加在另一个字符串的后面来解决
我们知道对于任意一个子串都是当前字符串的某一个后缀的前缀
预处理时,假设当前输入的两个字符串为s,p;我们将p加在s的h后面
那么求这两个字符串的最长公共子串，就转化为求某两个后缀的最长公共前缀
我们知道任意两个后缀的最长公共前缀一定是height数组中的某一个值
(对于sa[i]和sa[j] ,他们的最长公共前缀就是minheight[k](i<k<j);
那么答案是否就是height数组的最大值呢，答案是否定的，因为可能出现排名相邻的后缀来自于同一个子串
那么答案就很明显了。就是排名相邻的除去两个后缀都来自于相同字符串的height的最大值
代码如下：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 #define maxn 1000001 7 int wa[maxn*2+1],wb[maxn*2+1],wv[maxn*2+1],wq[maxn*2+1]; 8 int rank[maxn*2+1],sa[maxn*2+1]; 9 int r[maxn*2+1]; 10 int height[maxn*2+1]; 11 char s[maxn],p[maxn]; 12 int len1,len2,n; 13 int cmp(int *r,int a,int b,int l) 14 {return r[a]==r[b]&& r[a+l]==r[b+l];} 15 void da(int n,int m) 16 { 17 int i,j,p,*x=wa,*y=wb,*t; 18 for(i=0;i<m;i++) wq[i]=0; 19 for(i=0;i<n;i++) wq[x[i]=r[i]]++; 20 for(i=1;i<m;i++) wq[i]+=wq[i-1]; 21 for(i=n-1;i>=0;i--) sa[--wq[x[i]]]=i; 22 23 for(j=1,p=1;p<n;j*=2,m=p) 24 { 25 for(p=0,i=n-j;i<n;i++) y[p++]=i; 26 for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 27 for(i=0;i<n;i++) wv[i]=x[y[i]]; 28 for(i=0;i<m;i++) wq[i]=0; 29 for(i=0;i<n;i++) wq[wv[i]]++; 30 for(i=1;i<m;i++) wq[i]+=wq[i-1]; 31 for(i=n-1;i>=0;i--) sa[--wq[wv[i]]]=y[i]; 32 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) 33 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 34 } 35 return ; 36 } 37 void callheight(int n) 38 { 39 int i,j,k=0; 40 for(i=1;i<=n;i++) rank[sa[i]]=i; 41 for(i=0;i<n;i++) 42 { 43 if(k) k--; 44 j=sa[rank[i]-1]; 45 while(r[i+k]==r[j+k]) k++; 46 height[rank[i]]=k; 47 } 48 } 49 int main() 50 { 51 while(scanf("%s%s",s,p)!=EOF) 52 { 53 int len1=strlen(s); 54 int len2=strlen(p); 55 s[len1]='$'; 56 strcat(s,p); 57 n=strlen(s); 58 for(int i=0;i<n;i++) 59 r[i]=s[i]; 60 r[n]=0; 61 da(n+1,2*maxn+1); 62 callheight(n); 63 int ans=0; 64 for(int i=2;i<=n;i++) 65 { 66 if((sa[i]<len1 && sa[i-1]>len1)||(sa[i]>len1&&sa[i-1]<len1)) 67 ans=max(ans,height[i]); 68 } 69 cout<<ans<<endl; 70 71 } 72 return 0; 73 74 }