专栏首页数据结构与算法洛谷P4051 [JSOI2007]字符加密

洛谷P4051 [JSOI2007]字符加密

题目描述

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

例如‘JSOI07’,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1: 

JSOI07

输出样例#1: 

I0O7SJ

说明

对于40%的数据字符串的长度不超过10000。

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

很明显是后缀数组

一开始在纠结各个后缀的长度不同会不会影响到答案

后来想了一下不会。

因为我们所要求的后缀的前缀的长度都是相同的。

所以长度并不会影响到最终结果

然后愉快的背上模板就好啦

开始的时候按照套路把字符串复制一遍

// luogu-judger-enable-o2
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e6+10;
int sa[MAXN],tax[MAXN],rak[MAXN],tp[MAXN],a[MAXN],Height[MAXN],N,M;
char s[MAXN];
void Qsort()
{
    for(int i=0;i<=M;i++) tax[i]=0;
    for(int i=1;i<=N;i++) tax[rak[i]]++;
    for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
    for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort()
{
    M=200;
    for(int i=1;i<=N;i++) rak[i]=a[i],tp[i]=i;Qsort();
    for(int w=1,p=1; p<N ; M=p,w<<=1)
    {
        p=0;
        for(int i=1;i<=w;i++) tp[++p]=N-w+i;
        for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
        Qsort();swap(rak,tp);rak[sa[1]]=p=1;
        for(int i=2;i<=N;i++) 
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
    for(int i=1;i<=N;i++)
        if(sa[i]+N/2<=N)
            printf("%c",(char)a[sa[i]+N/2-1]);
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    scanf("%s",s);
    N=strlen(s);
    for(int i=0;i<N;i++) a[i+1]=s[i],a[i+N+1]=s[i];N=N*2;
    Ssort();    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3809 【模板】后缀排序

    题目背景 这是一道模板题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • 洛谷P2852 [USACO06DEC]牛奶模式Milk Patterns

    题目描述 Farmer John has noticed that the quality of milk given by his cows varies f...

    attack
  • BZOJ 2251 [2010Beijing Wc]外星联络

    Description 小 P 在看过电影《超时空接触》(Contact)之后被深深的打动,决心致力于寻 找外星人的事业。于是,他每天晚上都爬在屋顶上试图用自己...

    attack
  • 常用排序算法总结(2)

    朱晓霞
  • C/C++语言常用排序算法

    资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

    owent
  • ACM-ICPC 2018 徐州赛区网络预赛F. Features Track

    用户2965768
  • Leetcode题解——401/628

    这是题解系列上线后的第一篇文章,由于我刷的题目的难度目前都还是简单/中等,所以算法大神可以直接忽略我的文章了,文章中所给出的题解仅仅是作者个人的看法,欢迎各位读...

    出其东门
  • 1027 打印沙漏 (20 分)

    可爱见见
  • HDU-1054 Strategic Game(树形DP)

    Strategic Game Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32...

    ShenduCC
  • 最短路专题2 | CodeForces 449B - SPFA算法

    Jzzhu is the president of country A. There are n cities numbered from 1 to n in ...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动