P3809 【模板】后缀排序

题目背景

这是一道模板题。

题目描述

读入一个长度为

输入输出格式

输入格式：

一行一个长度为

输出格式：

一行，共n个整数，表示答案。

输入输出样例

输入样例#1：

ababa

输出样例#1：

5 3 1 4 2

说明

$10^6n<=106$

code

本题代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int N = 1000100;
 8 
 9 char s[N];
10 int sa[N],t1[N],t2[N],c[N];
11 int n,m = 130;
12 
13 void get_sa() {
14     int *x = t1,*y = t2;
15     for (int i=0; i<m; ++i) c[i] = 0;
16     for (int i=0; i<n; ++i) c[x[i] = s[i]]++;
17     for (int i=1; i<m; ++i) c[i] += c[i-1];
18     for (int i=n-1; i>=0; --i) sa[--c[x[i]]] = i;
19     for (int k=1; k<=n; k<<=1) {
20         int p = 0;
21         for (int i=n-k; i<n; ++i) y[p++] = i;
22         for (int i=0; i<n; ++i) if (sa[i] >= k) y[p++] = sa[i] - k;
23         for (int i=0; i<m; ++i) c[i] = 0;
24         for (int i=0; i<n; ++i) c[x[y[i]]]++;
25         for (int i=1; i<m; ++i) c[i] += c[i-1];
26         for (int i=n-1; i>=0; --i) sa[--c[x[y[i]]]] = y[i];
27         swap(x,y);
28         p = 1;
29         x[sa[0]] = 0;
30         for (int i=1; i<n; ++i)
31             x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && sa[i-1]+k<n && sa[i]+k<n &&    
32             y[sa[i-1]+k]==y[sa[i]+k]) ? p-1 : p++;       
33         if (p >= n) break;
34         m = p;
35     }
36 }
37 int main() {
38     scanf("%s",s);
39     n = strlen(s);
40     get_sa();
41     for (int i=0; i<n; ++i) 
42         printf("%d ",sa[i]+1);
43     return 0;    
44 }

View Code

后缀数组注释

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int N = 1000100;
 8 
 9 char s[N];
10 int sa[N],t1[N],t2[N],c[N],rnk[N],height[N];
11 //sa[i]  排名为i的是谁 -下标 
12 //rnk[i] i的排名 -名次 
13 //height[i]  排名为i的后缀与排名为i-1的后缀的最长公共前缀长度
14 int n,m = 130;
15 
16 void get_sa() {
17     int *x = t1,*y = t2;
18     //基数排序 
19     for (int i=0; i<m; ++i) c[i] = 0;
20     for (int i=0; i<n; ++i) c[x[i] = s[i]]++;
21     for (int i=1; i<m; ++i) c[i] += c[i-1];
22     for (int i=n-1; i>=0; --i) sa[--c[x[i]]] = i;
23     /*
24     每次循环
25     都将两个长度k子串合并为一个长度为2k的串
26     其中前k个字符构成的子串的排名为第一关键字，后k个字符为第二关键字
27     并求出合并后的字符串的排名 
28     */
29     //每次排名得到一共有多少个排名p，由p优化m的值。 
30     for (int k=1; k<=n; k<<=1) {
31         int p = 0;
32         /*
33         在上一轮中，第一关键字已经排好了， 此时只需要排第二关键字即可。 
34         y数组是第二关键字排序的结果，存储的是2k长度的字符串的第一关键字的下标 
35         n-k到n-1中所有的元素第二关键字为0 
36         */
37         for (int i=n-k; i<n; ++i) y[p++] = i;
38         for (int i=0; i<n; ++i) if (sa[i] >= k) y[p++] = sa[i] - k;
39         for (int i=0; i<m; ++i) c[i] = 0;
40         for (int i=0; i<n; ++i) c[x[y[i]]]++;
41         for (int i=1; i<m; ++i) c[i] += c[i-1];
42         for (int i=n-1; i>=0; --i) sa[--c[x[y[i]]]] = y[i];
43         swap(x,y);
44         p = 1;
45         x[sa[0]] = 0;
46         for (int i=1; i<n; ++i)
47             x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && sa[i-1]+k<n && sa[i]+k<n &&    
48             y[sa[i-1]+k]==y[sa[i]+k]) ? p-1 : p++;
49         if (p >= n) break;
50         m = p;
51     }
52 }
53 void get_height() {
54     for (int i=0; i<n; ++i) rnk[sa[i]] = i; // sa排名为i的下标，rnk[i]下标为i的后缀的名次。 
55     int k = 0; 
56     height[0] = 0;  
57     /*
58     性质：height[rnk[i]] >= height[rnk[i-1]]-1
59     理解为起始下标为i的后缀和i-1的后缀除了开头第一个字符不同，其余的相同的
60     即suffix[i,n]与suffix[i-1,n]只有第一个字符不同。 
61     所以suffix[i-1,n]匹配上的子串，与suffix[i,n]匹配的子串，中k-1个是相等的。
62     */ 
63     for (int i=0; i<n; ++i) {
64         if (!rnk[i]) continue; 
65         if (k) k--;
66         int j = sa[rnk[i]-1]; // 前一个排名的后缀的开始位置 
67         while (i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
68         height[rnk[i]] = k;
69     }
70 }
71 int main() {
72     scanf("%s",s);
73     n = strlen(s);
74     get_sa();
75     for (int i=0; i<n; ++i) 
76         printf("%d ",sa[i]+1);
77     return 0;    
78 }

View Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cctype>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
16     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
17 }
18 
19 const int N = 1000005;
20 char s[N];
21 int t1[N], t2[N], c[N], sa[N], rnk[N], height[N], n, m = 130;
22 
23 void getsa() {
24     int *x = t1, *y = t2, i, p;
25     for (i = 1; i <= m; ++i) c[i] = 0;
26     for (i = 1; i <= n; ++i) x[i] = s[i], c[x[i]] ++;
27     for (i = 1; i <= m; ++i) c[i] += c[i - 1];
28     for (i = n; i >= 1; --i) sa[c[x[i]]--] = i;
29     for (int k = 1; k <= n; k <<= 1) {
30         p = 0;
31         for (i = n - k + 1; i <= n; ++i) y[++p] = i;
32         for (i = 1; i <= n; ++i) if (sa[i] > k) y[++p] = sa[i] - k;
33         for (i = 1; i <= m; ++i) c[i] = 0;
34         for (i = 1; i <= n; ++i) c[ x[y[i]] ] ++;
35         for (i = 1; i <= m; ++i) c[i] += c[i - 1];
36         for (i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
37         swap(x, y);
38         x[sa[1]] = 1;
39         p = 2;
40         for (i = 2; i <= n; ++i) 
41             x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p - 1 : p ++;
42         if (p > n) break;
43         m = p;
44     }
45 }
46 void getheight() {
47     for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;
48     int k = 0;
49     height[1] = 0;
50     for (int i = 1; i <= n; ++i) {
51         if (rnk[i] == 1) continue;
52         if (k) k --;
53         int j = sa[rnk[i] - 1];
54         while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
55         height[rnk[i]] = k;
56     }
57 }
58 int main() {
59     scanf("%s",s + 1);
60     n = strlen(s + 1);
61     getsa();
62     getheight();
63     for (int i = 1; i <= n; ++i) printf("%d ",sa[i]);
64     return 0;
65 }

View Code