摘要:拆环为链后后缀排序

luogu4051[JSOI2007]字符加密

题面

题目分析

题目相当于是把一个环上的字符串拿来排序,那我们直接拆环为链,后缀排序即可.

然后后面长度不足以是一个原串的后缀忽略掉即可.

解释一下为什么是对的,因为按照字符串比较大小的方法,即使两个长度为原串的串后面接了一堆后缀,也不会影响排序的结果,结果仅与前面与原串长度相等的那一部分有关.

代码

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
63
64
65
66
67
68
69
70
71
72
73
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=200010;
lxl n,m=100,out;
lxl sa[big],suf[big],rank[big],tp[big],id[big];
char s[big],ans[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void QSort()
{
for(R int i(0);i<=m;++i)suf[i]=0;
for(R int i(1);i<=n;++i)++suf[rank[i]];
for(R int i(1);i<=m;++i)suf[i]+=suf[i-1];
for(R int i(n);i;--i)sa[suf[rank[tp[i]]]--]=tp[i];
}
inline void SuffixSort()
{
for(R int i(1);i<=n;++i)rank[i]=s[i]-'#',tp[i]=i;
QSort();
for(R int w(1),p(0);p<n;m=p,w<<=1)
{
p=0;
for(R int i(1);i<=w;++i)tp[++p]=n-w+i;
for(R int i(1);i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
QSort();
std::swap(tp,rank);
rank[sa[1]]=p=1;
for(R int i(2);i<=n;++i)
rank[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
}
}
int main(void)
{
scanf("%s",s+1);n=strlen(s+1);
for(R int i(1);i<=n;++i)id[i]=i;
for(R int i(n+1);i<=n+n-1;++i)s[i]=s[i-n];
n=n+n-1;
SuffixSort();
for(R int i(1);i<=n;++i)
{
if(!id[sa[i]])continue;
if(id[sa[i]]==1)ans[++out]=s[(n+1)/2];
else ans[++out]=s[id[sa[i]]-1];
}
for(R int i(1);i<=out;++i)printf("%c",ans[i]);endl;
return 0;
}