喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。
例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？
输入输出格式
输入格式：
输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。
输出格式：
输出一行，为加密后的字符串。
后缀数组裸题。
把字符串接到自己后面变成长度为2*len以后， 如何后求后缀排序得到sa数组和rak数组，对len长度的rak数组直接排序。
#include <iostream> #include <stdio.h> #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int tx[maxn], sa[maxn], rak[maxn]; int height[maxn]; int dp[maxn][20]; int lg[maxn]; char s[maxn]; int n, m, p, k; struct node { int x, y, id; }a[maxn], b[maxn]; void rsort() { for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[a[i].y]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = 1; i <= n; i++) { b[tx[a[i].y]--] = a[i]; } for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[b[i].x]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = n; i >= 1; i--) { a[tx[b[i].x]--] = b[i]; } } void ssort() { rsort(); p = 0; for (int i = 1; i <= n; i++) { if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) { ++p; } rak[a[i].id] = p; } for (int i = 1; i <= n; i++) { a[i].x = rak[i]; a[i].id = sa[rak[i]] = i; a[i].y = 0; } m = p; } void solve(int mx) { m = mx; for (int i = 1; i <= n; i++) { a[i].x = a[i].y = s[i]; a[i].id = i; } ssort(); for (int j = 1; j <= n; j <<= 1) { for (int i = 1; i + j <= n; i++) { a[i].y = a[i + j].x; } ssort(); if (p == n) { break; } } } char str[maxn]; struct query { int x, id; }q[maxn]; int cmp(query a, query b) { return a.x < b.x; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); scanf("%s", str + 1); int len = strlen(str + 1); for (int i = 1; i <= len; i++) { s[i] = str[i]; s[i + len] = str[i]; } n = 2 * len; solve(127); int ans = 0; for (int i = 1; i <= len; i++) { q[i].x = rak[i]; q[i].id = i; } sort(q + 1, q + len + 1, cmp); for (int i = 1; i <= len; i++) { printf("%c", s[q[i].id + len - 1]); } printf("\n"); return 0; } /* JSOI07 */
