Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 319|回复: 0

[默认分类] bzoj1031 [JSOI2007]字符加密Cipher

[复制链接]
  • TA的每日心情
    开心
    2021-12-13 21:45
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    发表于 2018-3-14 21:52:03 | 显示全部楼层 |阅读模式
    Description
     喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法
    :把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:
    JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序:07JSOI 7JSOI0 I07JSO JSOI07
    OI07JS SOI07J读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是
    突然想出来的,那就^^)。但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?
    对于100%的数据字符串的长度不超过100000。
    Solution
    本蒟蒻的第一题后缀数组SA,纪念一下
    把原串复制一份加在后面,跑出来的所有后缀中长度>=len的按顺序排序,每个取最后一位就ok
    膜来的板子a啊b啊c啊d啊乱七八糟的有点晕,但是想不到更好的替代
    辣鸡csdn,卡屎了
    Code
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <vector>
    #define rep(i,st,ed) for (int i=st;i<=ed;++i)
    #define drp(i,st,ed) for (int i=st;i>=ed;--i)
    #define fill(x,t) memset(x,t,sizeof(x))
    #define copy(x,t) memcpy(x,t,sizeof(x))

    const int N=200005;

    int rank[N],sa[N],h[N];
    int b[N],c[N],d[N];

    char s[N],ans[N];

    void get_sa(int n,int m) {
        rep(i,0,m) b[i]=0;
        rep(i,1,n) b[s[i]]++;
        rep(i,1,m) b[i]+=b[i-1];
        drp(i,n,1) c[b[s[i]]--]=i;
        int t=0;
        rep(i,1,n) {
            if (s[c[i]]!=s[c[i-1]]) t++;
            rank[c[i]]=t;
        }
        int j=1;
        while (j<=n) {
            rep(i,0,n) b[i]=0;
            rep(i,1,n) b[rank[i+j]]++;
            rep(i,1,n) b[i]+=b[i-1];
            drp(i,n,1) c[b[rank[i+j]]--]=i;
            rep(i,0,n) b[i]=0;
            rep(i,1,n) b[rank[i]]++;
            rep(i,1,n) b[i]+=b[i-1];
            drp(i,n,1) d[b[rank[c[i]]]--]=c[i];
            int t=0;
            rep(i,1,n) {
                if (rank[d[i]]!=rank[d[i-1]]||rank[d[i]]==rank[d[i-1]]&&rank[d[i]+j]!=rank[d[i-1]+j]) t++;
                c[d[i]]=t;
            }
            rep(i,1,n) rank[i]=c[i];
            if (t==n) break;
            j*=2;
        }
        rep(i,1,n)
            sa[rank[i]]=i;
    }

    void get_height(int n) {
        int k=0;
        rep(i,1,n) {
            if (k) k--;
            int j=sa[rank[i]-1];
            while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
            h[rank[i]]=k;
        }
    }

    int main(void) {
        scanf("%s", s); int len=strlen(s),m=0;
        drp(i,len,1) {
            s[i+len]=s[i]=s[i-1];
            m=std:: max(m,(int)s[i]);
        }
        get_sa(len*2,m);
        get_height(len*2);
        int j=0;
        rep(i,1,len*2) if (sa[i]<=len) ans[++j]=s[sa[i]+len-1];
        rep(i,1,len) printf("%c",ans[i]);
        return 0;
    }
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-12-23 02:19 , Processed in 0.338385 second(s), 34 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表