后缀数组定义后缀是什么是不言而喻的……
在后缀数组中，从第I个后缀开始的后缀称为第I个后缀。 (我个人习惯字符串下标从1开始。
这样我们就得到了n个后缀
根据倍增的思想，我们还可以在o(nLOGN ) o ) nlogn ) nlogn )的时间内对这n个后缀进行词典排序
变量名：
sa[i]:表示第排名I个后缀，表示第http://www.Sina.com/表示第排名I个后缀是第几个后缀
字符串aababb的后缀分别为：
ababbabbabbabbabbabbabbbbbbb首次将这些后缀的第一个字符作为关键字进行排序
[外部链接图像导出失败。 源站可能有防盗链机制。 我们建议您保存并直接上传图片。 (img-57 ug FAE3- 1614075926050 (c 3360 (users (typedef (pictures )笔记) 2021-02截图2021-02 ) )
结果是：
可以通过ababbababbabbabbbbbbbbbb基数排序，在o(n ) o ) o )时间内进行排序
我们想的文字每次都会加倍
如果我们用前k个字母决定顺序的话
那么，以前是以k个字符为第一关键词，以k~2k个字符为第二关键词进行基数排序
这样我们就用以前的2k文字决定了顺序
具体来说，每次排序后，将排序的最初k个字符离散化，将离散化的结果作为第一个关键词进行下一个循环
lg(n ) log ) n ) log ) n )轮后提示
最长公共前缀
:[ (外链图像导出失败。 源站可能有防盗链机制。 建议保存图像并直接上传(img-zXCEZ0ku-1614075926052 ) C : (用户(pictures )注释)基数. png
基数排序将每个数出现的次数保存在桶中
然后，通过桶和前缀，得到各自数量的排序那样的排列
为了确保排序的稳定性，在原始数组中用举个例子：更新等级，在更新等级的同时也更新前缀和数组
最终在o(n )-o )-n )-o )-n )的时间内获得各数的排序
那么，如何进行双关键词排序？
首先，用第二个关键词进行基数排序
然后，用第一关键字对排序结果进行排序
那样就可以了
那我们怎么得到第二个关键词？
据观察，第I个后缀第二个关键词实际上是第i k个后缀的第一个关键词
这样可以求出实现细节：第二关键字，请注意要考虑边界
height数组怎么求？
补充几个LCP的性质(I，j，k按词典顺序排序，rk[i]rk[k]rk[j] ) ) ) ) ) ) ) ) ) ) )
LCP(I，j
) = l c p ( j , i ) lcp(i,j)=lcp(j,i) lcp(i,j)=lcp(j,i) l c p ( i , i ) = l e n ( i ) lcp(i,i)=len(i) lcp(i,i)=len(i) l c p ( i , k ) = l c p ( k , j ) lcp(i,k)=lcp(k,j) lcp(i,k)=lcp(k,j) /************************************************************************* > File Name: p3809[模板]后缀排序.cpp > Author: typedef > Mail: 1815979752@qq.com > Created Time: 2021/2/23 7:43:45 ************************************************************************/#include<bits/stdc++.h>using namespace std;const int N=1e6+7;int n,m;char s[N];int sa[N],x[N],y[N],c[N],rk[N],height[N];//x是第一关键字,y是第二关键字,c是关键字的个数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 num=0;for(int i=n-k+1;i<=n;i++) y[++num]=i;for(int i=1;i<=n;i++)if(sa[i]>k) y[++num]=sa[i]-k;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;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;swap(x,y);x[sa[1]]=1,num=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])?num:++num;if(num==n) break;m=num;}return;}void get_height(){for(int i=1;i<=n;i++) rk[sa[i]]=i;for(int i=1,k=0;i<=n;i++){if(rk[i]==1) continue;if(k) k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;height[rk[i]]=k;}}int main(){scanf("%s",s+1);n=strlen(s+1),m=122;get_sa();//get_height();for(int i=1;i<=n;i++) printf("%d ",sa[i]);puts("");//for(int i=1;i<=n;i++) printf("%d ",height[i]);//puts("");return 0;}