后缀数组。

\(LCP(i,j)\)为\(suffix(sa[i])\)和\(suffix(sa[j])\)的最长公共前缀

\[LCP(i,j)=min(LCP(k,k-1)),i<=k<=j\]

\(height[i]\)表示\(LCP(i,i-1)\)

\(h[i]\)表示\(heigth[rank[i]]\)

\[h[i]>=h[i-1]-1\]

/*求sa数组，注意两个基数排序时循环要倒着。记得初始化m。m和n不要写混。*/void get_sa(){    for(int i=1;i<=n;i++) ++c[x[i]=s[i]];    for(int i=2;i<=m;i++) c[i]+=c[i-1];    for(int i=n;i;i--) sa[c[x[i]]--]=i;    for(int k=1;k<=n;k<<=1){        int p=0;        for(int i=n-k+1;i<=n;i++) y[++p]=i;        for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;  //y记录的是按照后半段排序的前半段位置        for(int i=1;i<=m;i++) c[i]=0;        for(int i=1;i<=n;i++) ++c[x[i]];        for(int i=2;i<=m;i++) c[i]+=c[i-1];        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];        swap(x,y);        x[sa[1]]=1,p=1;        for(int i=2;i<=n;i++)            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;        if(p==n) break;        m=p;    }}/*求heigth数组，大概就是与排名-1的那个后缀从上次的k-1位置开始比较。*/void get_ht(){    int k=0;    for(int i=1;i<=n;i++) rk[sa[i]]=i;    for(int i=1;i<=n;i++){        if(k) k--;  //h[i]>=h[i-1]-1        if(rk[i]==1) continue;          int j=sa[rk[i]-1];        while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;        ht[rk[i]]=k;    }}

应用

：参见国家集训队论文