巨佬博客： https://www.cnblogs.com/zwfymqz/p/8413523.html
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int n,M,sa[N],rk[N],tp[N],sum[N],hight[N]; char s[N]; void Qsort() { for(int i=0;i<=M;i++) sum[i]=0; for(int i=1;i<=n;i++) sum[rk[i]]++; for(int i=1;i<=M;i++) sum[i]+=sum[i-1]; for(int i=n;i>=1;i--) sa[ sum[rk[tp[i]]]-- ]=tp[i]; } void suffixsort() { M=100; for(int i=1;i<=n;i++) rk[i]=s[i]-‘0‘+1,tp[i]=i; Qsort(); for(int w=1,p=0;p<n;M=p,w<<=1) { p=0; for(int i=1;i<=w;i++)tp[++p]=n-w+i; for(int i=1;i<=n;i++) if(sa[i]>w)tp[++p]=sa[i]-w; Qsort(); swap(tp,rk); rk[sa[1]]=p=1; for(int i=2;i<=n;i++) rk[sa[i]]=( tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w] )?p:++p; } } void gethight() { int j,k=0; for(int i=1;i<=n;i++) { if(k)k--; int j=sa[rk[i]-1]; while(s[i+k]==s[j+k])k++; hight[rk[i]]=k; } } int main() { scanf("%s",s+1);n=strlen(s+1); suffixsort(); for(int i=1;i<=n;i++) printf("%d ",sa[i]); }
$sa[i]：排名为i的后缀的位置$
$rk[i]：从第i个位置开始的后缀的排名，下文为了叙述方便，把从第i个位置开始的后缀简称为后缀i$
$tp[i]：基数排序的第二关键字，意义与sa一样，即第二关键字排名为i的后缀的位置$
$sum[i]：ii号元素出现了多少次。辅助基数排序$
$s：字符串，s[i]表示字符串中第i个字符串$
$height[i]：lcp(sa[i],sa[i−1])，即排名为i的后缀与排名为i−1的后缀的最长公共前缀$
$一个人读取同一个字符串两次，因为机器的问题，每次读取可能会在原串的左边和右边加上一串随机字符串， 问原串的最大长度$
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; typedef long long ll; const int N=2e5+10; int n,M,sa[N],rk[N],tp[N],sum[N],height[N],lens,lens1; char s[N],s1[N]; void Qsort() { for(int i=0;i<=M;i++) sum[i]=0; for(int i=1;i<=n;i++) sum[rk[i]]++; for(int i=1;i<=M;i++) sum[i]+=sum[i-1]; for(int i=n;i>=1;i--) sa[ sum[rk[tp[i]]]-- ]=tp[i]; } void suffixsort() { M=100; for(int i=1;i<=n;i++) rk[i]=s[i]-‘0‘+1,tp[i]=i; Qsort(); for(int w=1,p=0;p<n;M=p,w<<=1) { p=0; for(int i=1;i<=w;i++)tp[++p]=n-w+i; for(int i=1;i<=n;i++) if(sa[i]>w)tp[++p]=sa[i]-w; Qsort(); swap(tp,rk); rk[sa[1]]=p=1; for(int i=2;i<=n;i++) rk[sa[i]]=( tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w] )?p:++p; } } void getheight() { int j,k=0; for(int i=1;i<=n;i++) { if(k)k--; int j=sa[rk[i]-1]; while(s[i+k]==s[j+k])k++; height[rk[i]]=k; } } bool ok(int x,int y) { if(x>y)swap(x,y); return x>=1&&x<=lens&&y>=lens+1&&y<=lens+lens1; } int main() { scanf("%s",s+1); lens=strlen(s+1); scanf("%s",s1+1); lens1=strlen(s1+1); strcat(s+1,s1+1); n=lens+lens1; suffixsort();getheight();int ans=0; for(int i=2;i<=lens+lens1;i++) if(ok(sa[i],sa[i-1]))ans=max(ans,height[i]); cout<<ans; }
原文：https://www.cnblogs.com/bxd123/p/11793833.html
