Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P4051 [JSOI2007]字符加密

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟
标签：        

P4051 [JSOI2007]字符加密

长度为 $n$ 的字符串，每次将第一个字符放在最后一个，一共可以得到 $n$ 个新的字符串，将它们从小到大排序，取每个串的最后一个字符，得到答案。

字符串排序，考虑后缀数组；每次将第一个字符放在最后一个，考虑将长度乘 $2$ ，破环成链，然后直接做 SA 。

对于长度不足的部分直接忽略。对于长度多出的部分，可以发现不影响排序。

例如题目中的 JSOI07 ，得到 JSOI07JSOI07 ，考察可行的部分。

1
2
3
4
5
6
7
JSOI07   ______
7JSOI0   7_____
07JSOI   07____
I07JSO   I07___
OI07JS   OI07__
SOI07J   SOI07_
JSOI07   JSOI07

对于范围内的部分，正常排序，如果前面一模一样，则多出的部分也一模一样，则空字符的字典序最小，因此会按照原来的顺序排序。

查看代码 
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int sa[N], rnk[N], ht[N], x[N], y[N], n, m, c[N];
void SA()
{
    for (int i = 1; i <= n; i++)
        c[x[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        c[i] += c[i - 1];
    for (int i = n; i; i--)
        sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; i++)
            y[++cnt] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                y[++cnt] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            c[i] = 0;
        for (int i = 1; i <= n; i++)
            c[x[i]]++;
        for (int i = 2; i <= m; i++)
            c[i] += c[i - 1];
        for (int i = n; i; i--)
            sa[c[x[y[i]]]--] = y[i];
        for (int i = 1; i <= n; i++)
            y[i] = x[i];
        for (int i = 1; i <= n; i++)
            x[i] = 0;
        x[sa[1]] = 1;
        cnt = 1;
        for (int i = 2; i <= n; i++)
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                x[sa[i]] = cnt;
            else
                x[sa[i]] = ++cnt;
        if (cnt == n)
            return;
        m = cnt;
    }
}
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        s[i + n] = s[i];
    n <<= 1;
    m = 300;
    SA();
    for (int i = 1; i <= n; i++)
        if (sa[i] <= (n >> 1))
            printf("%c", s[sa[i] + (n >> 1) - 1]);
    return 0;
}
相关文章