后缀数组 (后缀排序)suffix array
惯例: 直接放题 [模板] 后缀排序 https://www.luogu.com.cn/problem/P3809
学习来源 link https://www.cnblogs.com/zwfymqz/p/8413523.html
先口胡一下我对这玩意的理解吧
后缀是和前缀类似的东西, 学后缀的一般都学过前缀, 至少是前缀和呀啥的
但是一般后缀会针对字符串上的操作, 就像这个题里面 "把字符串的所有非空后缀按字典序从小到大排序"
后缀排序的实现主要依靠倍增法和基数排序来实现
先定义一些数组:
\(sa[i]:\) 排名为 \(i\) 的后缀的位置
\(rak[i]:\) 从第 \(i\) 个位置开始的后缀的排名, 下文为了叙述方便, 把从第 \(i\) 个位置开始的后缀简称为 "后缀 \(i\)"
\(tp[i]\): 基数排序的第二关键字, 意义与 \(sa\) 一样
\(tax[i]\):\(i\) 号元素出现了多少次. 辅助基数排序
观察易得:
\(rk[sa[i]]=i\space \space \space \space \space \space \space \space sa[rk[i]]=i\)
如果直接 sort 会爆掉复杂度, 因为我们的字符串长度和比较的时候复杂度和长度相关
所以我们就对每一位做文章
先是基数排序, 把所有的后缀按照第一位的字符排个序
然后考虑倍增
这里的倍增代码和 \(fft\) 的有一点点像
for(int w=1,p=0;p<n;m=p,w<<=1)
怕是天下倍增是一家
然后比较巧妙的一步就是在于 "\(i\) 号后缀的前 \(\frac{w}{2}\) 个字符形成的字符串是 \(i-\) \(\frac{w}{2}\) 号后缀的后 \(\frac{w}{2}\) 个字符形成的字符串"
这里大概需要意会我们去掉了后缀 \(i\) 的后面部分
我们每一次执行循环中的内容的时候有一个部分排好序的后缀数组 (可以意会的)
这里每一次考虑倍增新出来的那些位数, 对它们进行基数排序就可以了
- \(CODE:\)
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- namespace yspm {
- inline int read() {
- int res = 0, f = 1;
- char k;
- while (!isdigit(k = getchar()))
- if (k == '-')
- f = -1;
- while (isdigit(k)) res = res * 10 + k - '0', k = getchar();
- return res * f;
- }
- const int N = 1e6 + 10;
- char s[N];
- int n, m, rk[N], sa[N], tax[N], tp[N];
- inline void qsort() {
- memset(tax, 0, sizeof(tax));
- for (int i = 1; i <= n; ++i) tax[rk[i]]++;
- for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
- for (int i = n; i>= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
- return;
- }
- inline void work() {
- m = 75;
- for (int i = 1; i <= n; ++i) rk[i] = s[i] - '0' + 1, tp[i] = i;
- qsort();
- for (int w = 1, p = 0; p <n; m = p, w <<= 1) {
- p = 0;
- for (int i = 1; i <= w; ++i) tp[++p] = n - w + i;
- for (int i = 1; i <= n; ++i)
- if (sa[i]> w)
- tp[++p] = sa[i] - w;
- qsort();
- swap(tp, rk);
- rk[sa[1]] = p = 1;
- for (int i = 2; i <= n; ++i) {
- if (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])
- rk[sa[i]] = p;
- else
- rk[sa[i]] = ++p;
- }
- }
- for (int i = 1; i <= n; ++i) printf("%lld", sa[i]);
- return puts(""), void();
- }
- signed main() {
- scanf("%s", s + 1);
- n = strlen(s + 1);
- work();
- return 0;
- }
- } // namespace yspm
- signed main() { return yspm::main(); }
来源: http://www.bubuko.com/infodetail-3398743.html