#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#define pr(p) printf("%d\n",p)
const int oo=2147483640;
const int N=110000*2;
const int mod=1000000007;
using namespace std;
int tmp1[N],tmp2[N],cnt[N],SA[N],rank[N],height[N];
char s[N];
int main()
{
int n1,n;
scanf ("%s",s+1);
n1=n=strlen (s+1);
s[n+1]='#';
scanf ("%s",s+n+2);
n=strlen (s+n+2)+n+1;
int *x=tmp1,*y=tmp2,m=0;
for (int i=1; i<=n; i++) x[i]=s[i],m=max (m,x[i]);
memset (cnt,0,sizeof (cnt));
for (int i=1; i<=n; i++) cnt[x[i]]++;
for (int i=1; i<=m; i++) cnt[i]+=cnt[i-1];
for (int i=n; i>=1; i--) SA[cnt[x[i]]--]=i;
for (int L=1; L<=n; L<<=1)
{
int p=0;
for (int i=n-L+1; i<=n; i++) y[++p]=i;
for (int i=1; i<=n; i++) if (SA[i]>L) y[++p]=SA[i]-L;
memset (cnt,0,sizeof (cnt));
for (int i=1; i<=n; i++) cnt[x[y[i]]]++;
for (int i=1; i<=m; i++) cnt[i]+=cnt[i-1];
for (int i=n; i>=1; i--) SA[cnt[x[y[i]]]--]=y[i];
swap (x,y);
x[SA[1]]=m=1;
for (int i=2; i<=n; i++)
if (y[SA[i]]==y[SA[i-1]]&&y[SA[i]+L]==y[SA[i-1]+L]) x[SA[i]]=m;
else x[SA[i]]=++m;
if (m==n) break;
}
for (int i=1; i<=n; i++) rank[SA[i]]=i;
for (int i=1,k=0; i<=n; i++)
{
if (k>0) k--;
if (rank[i]>0) while (s[i+k]==s[SA[rank[i]-1]+k]) k++;
height[rank[i]]=k;
}
int ans=-oo;
for (int i=2; i<=n; i++)
{
int ma=max (SA[i-1],SA[i]);
int mi=min (SA[i-1],SA[i]);
if (ma>n1&&mi<=n1)
ans=max (ans,height[i]);
}
pr(ans);
return 0;
}
后缀数组为SA，SA[i]表示排完序后，排第i的后缀是哪个。（在原串中，开头位置为i的后缀，用i来表示，且从1开始编号）
另一个数组rank，rank[i]表示后缀i的排名。
显然rank[SA[i]]=i,SA[rank[i]]=i。
给出n个字符，用桶排将其稳定排序，输出排序后（按原来顺序的）字符的序号。
用s记录字符，用cnt数组统计每个字母出现次数，并记前缀和。
栗子：dabcba排序后aabbcd，cnt={2,2,1,1}->{2,4,5,6}
此时，cnt[i]表示第i个字母（注意是在字母表上的第几个，l为12,y为25,l又为12……）在原串中的最后一个的排名，如b最大排名为4。
现在从后往前枚举原串，假设现在枚举到i，则其排名为cnt[s[i]-'a'+1]，则A[ cnt[s[i]-'a'+1 ]=i。
字母s[i]的最后一个排名已经给出去了，下一个相同字母出现时，排名应往前一位，所以cnt[i]--。
memset(cnt,0,sizeof (cnt));
for (int i=1; i<=n; i++) cnt[s[i]]++;
for (int i=1; i<=26; i++) cnt[i]+=cnt[i-1];
for (int i=n; i>=1; i--)
{
A[ cnt[s[i] ]=i;
cnt[s[i]]--;
}
相当于双关键字排序。
由于桶排用的计数数组仅能装一个关键字，所以尝试一个一个关键字排序。
先按第二关键字稳定排序，按照此序列的顺序对第一关键字稳定排序即可。
memset(cnt,0,sizeof (cnt));//第二关键字
for (int i=1; i<=n; i++) cnt[s[i][2]]++;
for (int i=1; i<=26; i++) cnt[i]+=cnt[i-1];
for (int i=n; i>=1; i--) B[cnt[s[i][2]]--]=i;
memset(cnt,0,sizeof (cnt));//第一关键字
for (int i=1; i<=n; i++) cnt[s[B[i]][1]]++;
for (int i=1; i<=26; i++) cnt[i]+=cnt[i-1];
for (int i=n; i>=1; i--) A[ cnt[S[B[i]][1] ]--]=B[i];
//注意是按照第二关键字的排序结果B枚举的
给字符串的所有后缀排序。
首先，按第一个字符排序，再按前两个字符排序。。
然后按前4个字符排序。
此时每个关键字是两个字母，于是可将两个字母用数来表示（即用其排名来表示）。
有神魔用呢？？
注意到每个后缀的第3、4个字母必为另一个后缀的前两个字母，这样就将所有可能的双字符组转换成了数，比较数的大小即可。
用同样的方法可以给全部后缀排序。。。
每个后缀i的第二关键字，相当于后缀i+L的第一关键字。
上一轮的排序则将每个后缀的第一关键字排序了。
因此
当i+L>n，后缀i不存在第二关键字，这些后缀肯定排在最前面。
剩下的中，原来排在第一的是SA[1]，它开头L个字符是后缀SA[i]-L的第二关键字。所以下一个放进A的是SA[1]-L、SA[2]-L……
注意有些SA[i]<L，这些的前L个字符不是任何后缀的第二关键字，略去。
经过各种优化的代码见上……
计算每个后缀i与排在它前一个后缀i-1的LCP，记为height[i]。
（任意两后缀SA[x]、SA[y]的LCP为min(height[x+1],height[x+2],......,height[y])）
引理：height[rank[i]]>=height[rank[i-1]-1]
证明过程嘛，嘿嘿（省略四万字）
for (int i=1,k=0;i<=n;i++)//求height
{
if (k>0) k--;
if (rank[i]>0) while (s[i+k]==s[SA[rank[i]-1]+k]) ++k;
height[rank[i]]=k;
}
内容改写自Dark佬罗梓璋
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：后缀数组”