【BZOJ1031】【JSOI2007】字符加密cipher

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
这道题是后缀数组的模板题

Description

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

1

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0​把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07​ OI07JS SOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

Input

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

Output

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

Sample Input

$JSOI07$

Sample Output

$I0O7SJ$

Hint

对于$100$%的数据字符串的长度不超过$100000$。

题解

知识点：

后缀数组

分析：

题目要求求出的最后一列是什么，关键在于排序，但是就这样排又会出错（复杂度不对）。所以考虑把整个字符串倍长一次，这样是一定不会影响后缀的大小的，而且倍长一次之后相当于做到收尾相接，而且后缀的排序就等同于整个环串的排序。所以采用后缀数组给$2n$的字符串排序，然后扫一次判断$sa[i]$是否在$n$以内，是的话就是答案了，然后$sa[i]-1$的这个位置在原串中的内容就是答案了（这种方法要预处理出$s[0]=s[n]$,或者可以直接找$sa[i]+n-1$在倍长串中的内容也可以）。所以最终的时间复杂度与普通的后缀排序等价（尽管n变成了2倍），还是$O(n\log_{2}n)$。

我在这道题上 $WA​$ 了$5​$次，最后的问题是后缀数组中第$1​$次运算时的计数器$p​$没有清$0​$,导致有可能在进入循环判断的时候直接超过了字符集的大小$m​$，导致计算出错。这种低级错误一定要避免。

代码：

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=100010;//全都要开两倍空间，而且字符集初始大小定义为ASCII码的总数
int n,sa[maxn<<1],rnk[maxn<<1],y[maxn<<1],c[maxn<<1],m=128;
char s[maxn<<1];

void sort()
{
    int i;
    memset(c,0,sizeof(c));
    for (i=1;i<=n;i++)
        c[rnk[i]]++;
    for (i=2;i<=m;i++)
        c[i]+=c[i-1];
    for (i=n;i>=1;i--)
        sa[c[rnk[y[i]]]--]=y[i];
}

void getsa()//后缀排序的过程
{
    int p=0,k,i;//p一定要清0，否则会WA
    for (i=1;i<=n;i++)
    {
        rnk[i]=s[i];
        y[i]=i;
    }
    sort();
    for (k=1;k<=n&&p<n;k<<=1,m=p)
    {
        p=0;
        for (i=n-k+1;i<=n;i++)
            y[++p]=i;
        for (i=1;i<=n;i++)
            if (sa[i]>k)
                y[++p]=sa[i]-k;
        sort();
        swap(rnk,y);
        rnk[sa[1]]=p=1;
        for (i=2;i<=n;i++)
            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
    }
}

int main()
{
    int i;
    scanf("%s",s+1);
    n=strlen(s+1);
    for (i=1;i<=n;i++)//倍长字符串
        s[i+n]=s[i];
    n<<=1;
    getsa();
    n>>=1;
    s[0]=s[n];//首尾相接
    for (i=1;i<=(n<<1);i++)//判断是否在范围内，是的就是答案
        if (sa[i]<=n)
            putchar(s[sa[i]-1]);
    return 0;
}
显示 Gitment 评论