洛谷P4051 [JSOI2007]字符加密
2024-08-31 16:15:12
题目描述
喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。
例如‘JSOI07’,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?
输入输出格式
输入格式:
输入文件包含一行,欲加密的字符串。注意字符串的内容不一定是字母、数字,也可以是符号等。
输出格式:
输出一行,为加密后的字符串。
输入输出样例
说明
对于40%的数据字符串的长度不超过10000。
对于100%的数据字符串的长度不超过100000。
很明显是后缀数组
一开始在纠结各个后缀的长度不同会不会影响到答案
后来想了一下不会。
因为我们所要求的后缀的前缀的长度都是相同的。
所以长度并不会影响到最终结果
然后愉快的背上模板就好啦
开始的时候按照套路把字符串复制一遍
// luogu-judger-enable-o2
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e6+;
int sa[MAXN],tax[MAXN],rak[MAXN],tp[MAXN],a[MAXN],Height[MAXN],N,M;
char s[MAXN];
void Qsort()
{
for(int i=;i<=M;i++) tax[i]=;
for(int i=;i<=N;i++) tax[rak[i]]++;
for(int i=;i<=M;i++) tax[i]+=tax[i-];
for(int i=N;i>=;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort()
{
M=;
for(int i=;i<=N;i++) rak[i]=a[i],tp[i]=i;Qsort();
for(int w=,p=; p<N ; M=p,w<<=)
{
p=;
for(int i=;i<=w;i++) tp[++p]=N-w+i;
for(int i=;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
Qsort();swap(rak,tp);rak[sa[]]=p=;
for(int i=;i<=N;i++)
rak[sa[i]]=(tp[sa[i-]]==tp[sa[i]]&&tp[sa[i-]+w]==tp[sa[i]+w])?p:++p;
}
for(int i=;i<=N;i++)
if(sa[i]+N/<=N)
printf("%c",(char)a[sa[i]+N/-]);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
scanf("%s",s);
N=strlen(s);
for(int i=;i<N;i++) a[i+]=s[i],a[i+N+]=s[i];N=N*;
Ssort();
}
最新文章
- [vijos P1524] 最小监视代价
- 如何用myeclispe远程调试tomcat
- ch02-HTML的基本概念
- fscanf()函数具体解释
- Sql Server关于text类型的替换
- [Audio processing] 常见语音特征 —— LPC
- SharePoint webpart中悬浮窗口的webconfig路径
- iOS解析数据判断nil NULL Null的方法
- 编程算法 - 二叉树的深度 代码(C)
- Android Studio中.9.png文件出错问题
- 独立成分分析(ICA)的模拟实验(R语言)
- 异步请求引发的Chrome死锁
- (转)解决 TortoiseGit 诡异的 Bad file number 问题
- 13. The Impact of New Technology on Business 新科技对商务的影响
- 【Java深入研究】2、JDK 1.8 LinkedList源码解析
- centos7之docker安装
- Array数组内函数
- 用Jmeter+Badboy+Fiddler做接口测试
- hasattr getattr setattr delattr -->; (反射)
- oracle学习笔记一:用户管理(2)创建删除用户