洛谷P4051 [JSOI2007] 字符加密 题解

题目链接：P4051 [JSOI2007] 字符加密

题意：

喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。

例如 JSOI07，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0

把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J

读出最后一列字符：I0O7SJ，就是加密后的字符串

但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

输入格式：

输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。

输出格式：

输出一行，为加密后的字符串。

数据范围：

数据字符串的长度不超过 $10^5$。

先把原题的字符串复制一遍加到后面，然后跑一遍后缀排序

依次考虑每个后缀，如果它的编号小于等于 $n$ ，那这个串就是合法的，取 s[sa[i] + n - 1] 即可

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N], ans[N];
int t, sa[N], rk[N * 2], tmp[N * 2], cnt[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void solve(const int n)
{
    const int m = max(n, 666);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); int n = strlen(s + 1);
    for(int i = 1; i <= n; i++) s[n + i] = s[i];
    solve(2 * n);
    for(int i = 1; i <= 2 * n; i++)
        if(sa[i] <= n) ans[++t] = s[sa[i] + n - 1];
    cout << ans + 1 << '\n';
    return 0;
}

---

题外话：

话说这个怎么解密啊。