水题笔记_ [JSOI2007] 字符加密 [SA]

SB题

解决环状的问题 把整个序列复制一遍是手筋

懵逼的 题目

传送至 Bilibili

扯淡的 题解

唉…突然想起来当年我bzoj想做的第二道题就是这个…第一道是(想用EK做)狼抓兔子2333那时候好像想直接推出末尾的字符然后排序来着吧…唉…

今天本来想整理一下板子来着…结果先是MHR的锅++奇怪矩阵…又是Asia基本等于没讲的凸包…还有Diesheep和SLR的卖萌 + 卖弱…

so sad…

正好看着SA还不怎么会来着…于是搞了一波height…然后在CA爷爷的一句话题解里挑了个SA秒了…

这个题…连Height都不用求感觉非常资瓷啊

你只需要把整个序列都复制一遍, 然后求出所有后缀的排名即可, 这样就相当于给环上所有可能的字符串排序了…然后…输出就行了…

主要判断SA[i] <= (n >> 1)的时候才输出…因为排序的时候后面复制的串可能会排在前面…

要是SDOI的字符串也这么良心就好了…祈祷.jpg

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (200000 + 5)
using namespace std;
int n, a[MAXN], tmp[MAXN], rnk[MAXN], sa[MAXN], fir[MAXN], sec[MAXN], tong[MAXN];
char s[MAXN], sors[MAXN];
void initsa()
{
for (int i = 1; i <= n; i++) ++tong[a[i]];
for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
for (int i = 1; i <= n; i++) rnk[i] = tong[a[i] - 1] + 1;

for (int t = 1; t <= n; t <<= 1)
{
for (int i = 1; i <= n; i++) fir[i] = rnk[i];
for (int i = 1; i <= n; i++) sec[i] = ((i + t > n) ? 0 : rnk[i + t]);

fill(tong, tong + n + 1, 0);
for (int i = 1; i <= n; i++) ++tong[sec[i]];
for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
for (int i = 1; i <= n; i++) tmp[n - --tong[sec[i]]] = i;

fill(tong, tong + n + 1, 0);
for (int i = 1; i <= n; i++) ++tong[fir[i]];
for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
for (int j = 1, i; j <= n; j++) i = tmp[j], sa[tong[fir[i]]--] = i;

bool ok = true;
for (int j = 1, last = 0, i; j <= n; j++)
{
i = sa[j];
if (!last) rnk[i] = 1;
else if (fir[i] == fir[last] && sec[i] == sec[last]) rnk[i] = rnk[last], ok = false;
else rnk[i] = rnk[last] + 1;
last = i;
}
if (ok) break;
}
}
int main()
{
scanf("%s", s);
n = strlen(s);
strcpy(sors, s);
for (int i = n; i < (n << 1); i++)
s[i] = s[i - n];
sort(sors, sors + n);
n <<= 1;
int tn = unique(sors, sors + n) - sors - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(sors, sors + tn, s[i - 1]) - sors + 1;
initsa();
for (int i = 1; i <= n; i++)
if (sa[i] <= (n >> 1))
printf("%c", sors[a[sa[i] + (n >> 1) - 1] - 1]);
return 0;
}

// I0O7SJ
// 1234: 1234 2341 32

By 沙茶 Cansult