POJ2774 Long Long Message 后缀数组

　　两个字符串的最长公共字串。
　　求出height数组后直接二分答案就可以了，或者线性扫描一遍。
  1 //STATUS:C++_AC_594MS_4800KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL __int64
 15 #define pii pair<int,int>
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define lson l,mid,rt<<1
 18 #define rson mid+1,r,rt<<1|1
 19 #define PI acos(-1.0)
 20 const int N=200010,INF=0x3f3f3f3f,MOD=10000,STA=8000010;
 21 //const LL LNF=0x3f3f3f3f3f3f3f3f;
 22 const double DNF=1e13;
 23 //
 24 inline int Max(int a,int b){return a>b?a:b;}
 25 inline int Min(int a,int b){return a<b?a:b;}
 26 void swap(int& a,int& b){int t=a;a=b;b=t;}
 27 void swap(LL& a,LL& b){LL t=a;a=b;b=t;}
 28 //
 29 
 30 char s[N/2];
 31 int num[N];
 32 int sa[N],t1[N],t2[N],c[N],rank[N],height[N];
 33 int n,m,len1,len2;
 34 
 35 void build_sa(int s[],int n,int m)
 36 {
 37     int i,k,p,*x=t1,*y=t2;
 38     //第一轮基数排序
 39     for(i=0;i<m;i++)c[i]=0;
 40     for(i=0;i<n;i++)c[x[i]=s[i]]++;
 41     for(i=1;i<m;i++)c[i]+=c[i-1];
 42     for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
 43     for(k=1;k<=n;k<<=1){
 44         p=0;
 45         //直接利用sa数组排序第二关键字
 46         for(i=n-k;i<n;i++)y[p++]=i;
 47         for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
 48         //基数排序第一关键字
 49         for(i=0;i<m;i++)c[i]=0;
 50         for(i=0;i<n;i++)c[x[y[i]]]++;
 51         for(i=1;i<m;i++)c[i]+=c[i-1];
 52         for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
 53         //根据sa和x数组计算新的x数组
 54         swap(x,y);
 55         p=1;x[sa[0]]=0;
 56         for(i=1;i<n;i++)
 57             x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 58         if(p>=n)break;   //已经排好序，直接退出
 59         m=p;     //下次基数排序的最大值
 60     }
 61 }
 62 
 63 void getHeight(int s[],int n)
 64 {
 65     int i,j,k=0;
 66     for(i=0;i<=n;i++)rank[sa[i]]=i;
 67     for(i=0;i<n;i++){
 68         if(k)k--;
 69         j=sa[rank[i]-1];
 70         while(s[i+k]==s[j+k])k++;
 71         height[rank[i]]=k;
 72     }
 73 }
 74 
 75 int binary(int l,int r)
 76 {
 77     int i,j,mid,ok1,ok2,ret;
 78     while(l<=r){
 79         mid=(l+r)>>1;
 80         ok1=ok2=0;
 81         if(sa[1]<len1)ok1=1;
 82         else if(sa[1]>len1)ok2=1;
 83         for(i=2;i<=n;i++){
 84             if(height[i]<mid)ok1=ok2=0;
 85             if(sa[i]<len1)ok1=1;
 86             else if(sa[i]>len1)ok2=1;
 87             if(ok1 && ok2)break;
 88         }
 89         if(ok1 && ok2)ret=mid,l=mid+1;
 90         else r=mid-1;
 91     }
 92     return ret;
 93 }
 94 
 95 int main()
 96 {
 97  //   freopen("in.txt","r",stdin);
 98     int i,j;
 99     while(~scanf("%s",s) && s[0]!='#')
100     {
101         len1=strlen(s);
102         for(i=0;i<len1;i++)num[i]=s[i]-'a'+1;
103         num[len1]=27;
104         scanf("%s",s);
105         len2=strlen(s);
106         n=len1+len2+1;
107         for(i++,j=0;i<n;i++,j++)num[i]=s[j]-'a'+1;
108         num[n]=0;
109         m=28;
110         build_sa(num,n+1,m);
111         getHeight(num,n);
112 
113         printf("%d\n",binary(0,Min(len1,len2)));
114     }
115     return 0;
116 }