Longest Common Substring

/*----------------------------------------------File: F:\ACM源代码\数据结构--后缀数组\Longest_Common_Substring.cppDate: 2017/5/30 16:55:36Author: LyuCheng----------------------------------------------*//*题意：最长公共子序列思路：问题很多，DP基本不用考虑，因为时间复杂度空间复杂度都不允许，NlogN的算法也不行，最坏的情况    转化成LIS的数组是1e10空间复杂的不允许，所以只能利用后缀数组的性质，将两个连接，然后前后两个    前缀在两个不同的字符串中的时候，更新height的值，因为后缀加前缀，刚好是公共子序列*/#include <bits/stdc++.h>#define MAXN 100005using namespace std;char s1[MAXN],s2[MAXN];/****************************************后缀数组模板****************************************/const int maxn=1000000+100;struct SuffixArray{    char s[maxn];    int sa[maxn],rank[maxn],height[maxn];    int t1[maxn],t2[maxn],c[maxn],n;    int dmin[maxn][20];    void build_sa(int m)    {        int i,*x=t1,*y=t2;        for(i=0;i<m;i++) c[i]=0;        for(i=0;i<n;i++) c[x[i]=s[i]]++;        for(i=1;i<m;i++) c[i]+=c[i-1];        for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;        for(int k=1;k<=n;k<<=1)        {            int p=0;            for(i=n-k;i<n;i++) y[p++]=i;            for(i=0;i<n;i++)if(sa[i]>=k) y[p++]=sa[i]-k;            for(i=0;i<m;i++) c[i]=0;            for(i=0;i<n;i++) c[x[y[i]]]++;            for(i=1;i<m;i++) c[i]+=c[i-1];            for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]] = y[i];            swap(x,y);            p=1,x[sa[0]]=0;            for(i=1;i<n;i++)                x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]? p-1:p++;            if(p>=n) break;            m=p;        }    }    void build_height()//n不能等于1,否则出BUG    {        int i,j,k=0;        for(i=0;i<n;i++)rank[sa[i]]=i;        for(i=0;i<n;i++)        {            if(k)k--;            j=sa[rank[i]-1];            while(s[i+k]==s[j+k])k++;            height[rank[i]]=k;        }    }    void initMin()    {        for(int i=1;i<=n;i++) dmin[i][0]=height[i];        for(int j=1;(1<<j)<=n;j++)            for(int i=1;i+(1<<j)-1<=n;i++)                dmin[i][j]=min(dmin[i][j-1] , dmin[i+(1<<(j-1))][j-1]);    }    int RMQ(int L,int R)//取得范围最小值    {        int k=0;        while((1<<(k+1))<=R-L+1)k++;        return min(dmin[L][k] , dmin[R-(1<<k)+1][k]);    }    int LCP(int i,int j)//求后缀i和j的LCP最长公共前缀    {        int L=rank[i],R=rank[j];        if(L>R) swap(L,R);        L++;//注意这里        return RMQ(L,R);    }}sa;/****************************************后缀数组模板****************************************/int main(){    // freopen("in.txt","r",stdin);    while(scanf("%s%s",s1,s2)!=EOF){        int n=strlen(s1);        int m=strlen(s2);        for(int i=0;i<n;i++){            sa.s[i]=s1[i];        }        sa.s[n]=‘$‘;        for(int i=n;i<n+m;i++){            sa.s[i]=s2[i-n];        }        sa.n=m+n+1;        sa.build_sa(MAXN);        sa.build_height();        int maxLCS=-1;        for(int i=0;i<m+n+1;i++){            if(i==0){                maxLCS=max(maxLCS,sa.height[i]);            }else{                if((sa.sa[i]-n)*(sa.sa[i-1]-n)<0)//保证两后缀是来自不同的字符串的                    maxLCS=max(maxLCS,sa.height[i]);            }        }        printf("%d\n",maxLCS);    }    return 0;}