1 #include "stdio.h" 2 #include "string.h" 3 #define maxn 200010 4  5 int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; 6 int rank[maxn],height[maxn]; 7 int r[maxn],sa[maxn]; 8 char s1[100010],s2[100010]; 9 int n,l1,l2,ans;10 11 int cmp(int *r,int a,int b,int l)12 {13     return r[a]==r[b]&&r[a+l]==r[b+l];14 }15 16 void da(int *r,int *sa,int n,int m)17 {18     int i,j,p,*x=wa,*y=wb,*t;19     for(i=0; i<m; i++) ws[i]=0;20     for(i=0; i<n; i++) ws[x[i]=r[i]]++;21     for(i=1; i<m; i++) ws[i]+=ws[i-1];22     for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;23     for(j=1,p=1; p<n; j*=2,m=p)24     {25 26         for(p=0,i=n-j; i<n; i++) y[p++]=i;27         for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;28         for(i=0; i<n; i++) wv[i]=x[y[i]];29         for(i=0; i<m; i++) ws[i]=0;30         for(i=0; i<n; i++) ws[wv[i]]++;31         for(i=1; i<m; i++) ws[i]+=ws[i-1];32         for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];33         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)34             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;35     }36     return;37 }38 39 void calheight(int *r,int *sa,int n)40 {41     int i,j,k=0;42     for(i=1; i<=n; i++) rank[sa[i]]=i;43     for(i=0; i<n; height[rank[i++]]=k)44         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);45     return;46 }47 48 bool _same(int lx,int ly,int l1,int l2)49 {50     return (((lx<=l1-1) && (ly>=l1+1))||((ly<=l1-1) && (lx>=l1+1)));51 }52 53 //da(r,sa,n+1,128);54 //calheight(r,sa,n);55 int main()56 {57     scanf("%s",s1);58     l1=strlen(s1);59     scanf("%s",s2);60     l2=strlen(s2);61     for (int i=0;i<l1;i++)62     {63         char ch=s1[i];64         int tmp=ch-‘a‘+2;65         r[i]=tmp;66     }67     r[l1]=99;68     for (int i=l1+1;i<l1+l2+1;i++)69     {70         char ch=s2[i-l1-1];71         int tmp=ch-‘a‘+2;72         r[i]=tmp;73     }74     n=l1+l2+1;75     r[n]=0;76 77     da(r,sa,n+1,128);78     calheight(r,sa,n);79 80     ans=0;81     for (int i=1;i<=n;i++)82     {83         int t1=sa[i],t2=sa[i-1];84         if (_same(t1,t2,l1,l2))85         {86             if (height[i]>ans)87                 ans=height[i];88         }89     }90     printf("%d\n",ans);91 92     return 0;93 }