题解 P3809 【【模板】后缀排序】

Nemlit

2019-08-28 09:49:06

Solution

后缀数组是一个思路较为清晰,代码十分玄学的操作,~~建议大家按照代码模拟一下样例,理解每一步操作的意义~~ 后缀数组的作用是将长度为N的字符串的N个后缀来进行排序 我们直接排序的复杂度是$O(N^2logN)$ 后缀数组常用方法是倍增+基数排序算法: ## 1.基数排序 我们先来看一下代码:(默认升序排列) ```cpp //rep(i, a, b)是正序从a-b枚举 //drep(i, a, b)是倒序从a-b枚举 //a数组为基数排序辅助数组,即为一个桶 //rk数组为基数排序的第一关键字 //tp第二关键字中,排名为i的数的位置 //sa数组可以在此处理解为排完序后排名为i的数对的位置 il void Qsort() { rep(i, 1, m) a[i] = 0;// rep(i, 1, n) ++ a[rk[i]]; rep(i, 1, m) a[i] += a[i - 1]; //记录前缀和以后,a[i]的意义是rak为i的数最大可以到哪里 drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i]; //-- a的意义是减少了一个位置,所以a最大可以到的位置往前移一个 } ``` 我们来模拟一下,假设我们要对一个数组进行基数排序 其中第一关键字为:$1\ 3\ 2\ 1\ 4\ 3\ 1\ 2$ 对应第二关键字为:$3\ 2\ 1\ 2\ 3\ 3\ 1\ 3$ 所以对应$tp$数组为:$3\ 7\ 2\ 4\ 1\ 5\ 6\ 8$ ### 第一步 我们清空桶 ### 第二步 我们将第一关键字压入桶中,得到a数组:$3\ 2\ 2\ 1$ ### 第三步 我们将a数组记录前缀和,得到a数组:$3\ 5\ 7\ 8$ 然后我们就可以发现一个奇妙的性质 对与第一关键字为1的数对,他们的排名为$1-3$ 对与第一关键字为2的数对,他们的排名为$4-5$ 对与第一关键字为3的数对,他们的排名为$6-7$ 对与第一关键字为4的数对,他们的排名为$8-8$ 所以从某种意义上来说,我们已经对第一关键字排好了序 ### 第四步 我们从前往后倒序枚举 首先,最后一个数对的第二关键字为8,第8个数对的第一关键字为2,2的桶现在为5,所以排名为5的位置是第8个 然后2的桶减一,因为第五个位置已经被占用,所以第一关键字为2的数对排名为$4-4$ 第7个数对的第二关键字为6,第六个数的第一关键字的桶为7个,于是排名为7的位置是第6个 以此类推,我们可以拍好序,最后的sa数组为$7\ 4\ 1\ 3\ 8\ 2\ 6\ 5$ ## 2.倍增 ### 定义: $1.\ <a, b>$为以a为第一关键字,b为第二关键字进行基数排序) $2.\ s[i]$表示原数组的第i位字符 $3.\ i-$后缀表示对字符串S的每个后缀,取左边i个字符,得到一个i-后缀 $4.\ rk[i][j]$表示第j位上的i-后缀的排名 ### 操作: 我们可以先按$<i, s[i]>$进行基数排序,得到$rk[1][i]$ 再按照$<rk[1][i], rk[1][i + 1]>$进行基数排序,得到$rk[2][i]$ 因为是倍增,所以我们可以通过$<rk[2][i], rk[2][i + 2]>$进行基数排序,得到$rk[4][i]$ 同理,我们也可以用$<rk[4][i], rk[4][i + 4]>$进行基数排序,得到$rk[8][i]$ 当所有$rk[2^k][i]$互不相同,排序结束 代码如下(倍增部分代码有详细注释,就不模拟了,各位最好手动模拟,理解每一行代码,注意在模拟的时候分清楚rk[i]和sa[i]的区别,一定要先清楚每一个数组的意义!!!): ```cpp #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define _ 1000005 int n, m, a[_], sa[_], rk[_], tp[_]; char c[_]; /* sa[i]:排名为i的后缀的位置 rk[i]:第i个位置开始的后缀的排名,作为基数排序的第一关键字 tp[i]:第二关键字中,排名为i的数的位置 a[i]:有多少个元素排名为i c[i]:原输入数组 */ il int get(char c) { if(c >= '0' && c <= '9') return c - '0' + 1; if(c >= 'A' && c <= 'Z') return c - 'A' + 11; return c - 'a' + 37; } il void init() { rep(i, 1, n) rk[i] = get(c[i]), tp[i] = i; } il void print() { rep(i, 1, n) printf("%d ", sa[i]); } il void Qsort() { rep(i, 1, m) a[i] = 0; rep(i, 1, n) ++ a[rk[i]]; rep(i, 1, m) a[i] += a[i - 1]; //记录前缀和以后,a[i]的意义是rak为i的数最大可以到哪里 drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i]; //-- a的意义是减少了一个位置,所以a最大可以到的位置往前移一个 } il void get_sort() { for(re int w = 1, p = 0; w <= n; m = p, p = 0, w <<= 1) { //p在此时的意义是最高出现的排名以及一个计数器 //p < n的意义是如果当前最大排名== n则无继续排序的意义 rep(i, n - w + 1, n) tp[++ p] = i; //这里p的定义只是一个计数器 //tp[i]表示第二关键字中,排名为i的数的位置 //因为i - w + 1后面没有第二关键字,所以要补0 //所以要设成极小值排在前面 rep(i, 1, n) if(sa[i] > w) tp[++ p] = sa[i] - w; //在第一关键字中排名越靠前,表示应该排在前面 Qsort(), swap(rk, tp), p = rk[sa[1]] = 1; //我们现在更新rk,tp已经无用,先备份,用memcpy也行 //注意到一个性质 : rk[sa[i]] = i rep(i, 2, n) rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++ p; //注意tp和rk已经交换,所以这个判断的意思是: //如果两个后缀还相等,则排名不变,否则++ if(p == n) return; } } int main() { scanf("%s", c + 1), n = strlen(c + 1), m = 62; init(), Qsort(), get_sort(), print(); return 0; } ```