P3809 【模板】后缀排序题解

yhy-trh / 2023-05-04 / 原文

一、题目描述：

　　给你一个长度为 $n$ 的字符串，由大小写英文字母和数字组成。请将这个字符串的所有非空后缀按字典序排序，顺序输出后缀的第一个字符在原串中的位置，编号为 $1$ 到 $n$。

二、解题思路：

　　板子题，我就不写思路了。我用的是 $SA$，$DC3$ 还没学。时间复杂度 $O(nlogn)$。

三、完整代码：

 1 #include<iostream>
 2 #define N 1000010
 3 using namespace std;
 4 string s;
 5 int n,p,m=122,sa[N],rak[N],tp[N];
 6 struct ST{
 7     int l,r,id;
 8     bool operator != (const ST &d)const{
 9         if(d.l!=l)    return 1;
10         if(d.r!=r)    return 1;
11         return 0;
12     }
13 }q[N],h[N];
14 void qsort()
15 {
16     for(int i=0;i<=m;i++)    tp[i]=0;
17     for(int i=1;i<=n;i++)    tp[q[i].r]++;
18     for(int i=1;i<=m;i++)    tp[i]+=tp[i-1];
19     for(int i=n;i>=1;i--)    h[tp[q[i].r]--]=q[i];
20     for(int i=0;i<=m;i++)    tp[i]=0;
21     for(int i=1;i<=n;i++)    tp[h[i].l]++;
22     for(int i=1;i<=m;i++)    tp[i]+=tp[i-1];
23     for(int i=n;i>=1;i--)    q[tp[h[i].l]--]=h[i];
24 }
25 void suffixsort()
26 {
27     for(int i=1;i<=n;i++)
28         rak[i]=s[i-1];
29     for(int i=1;i;i<<=1,m=p)
30     {
31         for(int j=1;j<=n;j++)
32         {
33             q[j].id=j;
34             q[j].l=rak[j];
35             if(j+i>n)    q[j].r=0;
36             else    q[j].r=rak[j+i];
37         }
38         qsort();    p=0;
39         for(int j=1;j<=n;j++)
40         {
41             p+=q[j]!=q[j-1];
42             rak[q[j].id]=p;
43         }
44         if(p==n)    break;
45     }
46     for(int i=1;i<=n;i++)
47         sa[rak[i]]=i;
48     for(int i=1;i<=n;i++)
49         cout<<sa[i]<<" ";
50 }
51 int main()
52 {
53     ios::sync_with_stdio(false);
54     cin.tie(0);cout.tie(0);
55     cin>>s;
56     n=s.length();
57     suffixsort();
58     return 0;
59 }