[JSOI2007] 字串加密

题链：luogu

JS同学？

Description

让JS同学对环形字符串进行重组加密。加密规则是：

列出 \(n\) 个字符串并字典序升序，一次取末尾字符作为加密后的长度为 \(n\) 的密码串。

Analysis

看到字典序升序、共 \(n\) 个字串等关键词，你不由地想到了后缀数组（\(\text{Suffix Array}\)，\(\text{SA}\)）算法。

回忆你曾经学过的 \(\text{SA}\) 算法，感到十分生疏，只记得 \(sa_i\) 是表示原序列第 \(sa_i\) 个字符开始的后缀字串在字典序升序后的 \(\text{rank}\) 为 \(i\)，你束手无措，但转而想到貌似只需要会求 \(sa_i\) 即可。

先不考虑环形，题目中让我们求最后一个字符，你想到 \(sa_i\) 求的是第一个字符位置，貌似有所联系；考虑环形，最后一个字符的后一个字符就是第一个字符，故只需知道第一个字符的位置，\(-1\) 即为最后字符的位置（注意循环，勿越界）。

但是通常 \(\text{SA}\) 只考虑非环情况，若要考虑环，常见做法是 \(2\times n\)，于是你决定 s[i+n] = s[i]。可惜的是这样你在最后会发现有 \(2\times n\) 个 \(sa_i\)，你不知道该选哪一个输出。

回归 \(sa_i\) 的定义，得知为 开头字符在原序列中的位置，故只有 \(sa_i\) 不超过 \(n\) 时，你才需要输出答案 \(s_{sa_i-1}\)。

看样例，得知 \(sa_1\) 为 \(11>6\)，舍弃；\(sa_2\) 为 \(5<6\)，可用，故首个输出字符为 \(s_{5-1}=s_4=\text{I}\)；后面以此类推。

Code

#include <stdio.h>
#include <string.h>
#include <iostream>
const int N = (int)1e6 + 5;
char s[N << 1]; int n, m, sa[N], rk[N], tp[N], tax[N];
inline void Rsort() { //基数排序
	for (int i = 1; i <= m; ++i) tax[i] = 0;
	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];
}
inline void Csort() { //getSA
	for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
	Rsort();
	for (int w = 1, temp; temp < n && w <= n; m = temp, w <<= 1) {
		temp = 0; for (int i = n - w + 1; i <= n; ++i) tp[++temp] = i;
		for (int i = 1; i <= n; ++i)
			if (sa[i] > w) tp[++temp] = sa[i] - w;
		Rsort(); std:: swap(rk, tp); rk[sa[1]] = temp = 1;
		for (int i = 2; i <= n; ++i)
			rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? temp : ++temp;
	}
}
int main(void) {
	freopen("cipher.in", "r", stdin); freopen("cipher.out", "w", stdout);
	scanf("%s", s + 1);
	n = strlen(s + 1); m = (1 << 7) - 1;
	for (int i = 1; i <= n; ++i) s[n + i] = s[i]; n <<= 1;
	Csort();
	for (int i = 1; i <= n; ++i)
		if (sa[i] <= n / 2) putchar(s[(sa[i] - 1 + n - 1) % n + 1]); putchar('\n'); //找答案
	return 0;
}

The end. Thanks.

（走过路过，一定赞过qwq