复杂度：O(nlogn)

注：从0到n-1

```cpp

const int maxn=1e5;

char s[maxn];

int sa[maxn],Rank[maxn],height[maxn],rmq[maxn][50];

void build()

{

//sa[]

int n=strlen(s),m=128;

static int x[maxn],y[maxn],c[maxn];

for(int i=0;i<m;++i)c[i]=0;

for(int i=0;i<n;++i)c[x[i]=s[i]]++;

for(int i=1;i<m;++i)c[i]=c[i]+c[i-1];

for(int i=n-1;i>=0;--i)sa[--c[x[i]]]=i;

for(int k=1;k<=n;k<<=1)

{

int p=0;

for(int i=n-k;i<n;++i)y[p++]=i;

for(int i=0;i<n;++i)if(sa[i]>=k)y[p++]=sa[i]-k;

for(int i=0;i<m;++i)c[i]=0;

for(int i=0;i<n;++i)c[x[y[i]]]++;

for(int i=1;i<m;++i)c[i]+=c[i-1];

for(int i=n-1;i>=0;--i)sa[--c[x[y[i]]]]=y[i];

swap(x,y);

p=1;x[sa[0]]=0;

for(int i=1;i<n;++i)x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

if(p>=n)break;

m=p;

}

//Rank[]

for(int i=0;i<n;++i)Rank[sa[i]]=i;

//height[]

int len=0;

for(int i=0;i<n;++i)

{

if(len)len--;

if(Rank[i]==0)continue;

int j=sa[Rank[i]-1];

while(s[i+len]==s[j+len])len++;

height[Rank[i]]=len;

}

//rmq[][]

for(int i=1;i<n;++i)rmq[i][0]=height[i];

for(int i=1;(1<<i)<n;++i)for(int j=1;j+(1<<i)<=n;++j)rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);

}

int lcp(int a,int b)//a,b为两后缀的字典序排名

{

if(a==b)return strlen(s+sa[a]);

if(a>b)swap(a,b);

int k=0;

while((1<<(k+1))<=b-a)k++;

return min(rmq[a+1][k],rmq[b-(1<<k)+1][k]);

}