題目描述

喜歡鉆研問題的JS 同學(xué)，最近又迷上了對(duì)加密方法的思考。一天，他突然想出了一種他認(rèn)為是終極的加密辦法：把需要加密的信息排成一圈，顯然，它們有很多種不同的讀法。

例如‘JSOI07’，可以讀作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它們按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 讀出最后一列字符：I0O7SJ，就是加密后的字符串（其實(shí)這個(gè)加密手段實(shí)在很容易破解，鑒于這是突然想出來的，那就^^）。 但是，如果想加密的字符串實(shí)在太長(zhǎng)，你能寫一個(gè)程序完成這個(gè)任務(wù)嗎？

輸入格式
輸入文件包含一行，欲加密的字符串。注意字符串的內(nèi)容不一定是字母、數(shù)字，也可以是符號(hào)等。

輸出格式
輸出一行，為加密后的字符串。

輸入輸出樣例
輸入 #1復(fù)制

JSOI07

輸出 #1復(fù)制

I0O7SJ

說明/提示
對(duì)于40%的數(shù)據(jù)字符串的長(zhǎng)度不超過10000。

對(duì)于100%的數(shù)據(jù)字符串的長(zhǎng)度不超過100000。

題解：

樣例分析：
JSOI07排序后

07JSOI7JSOI0 I07JSO JSOI07 OI07JS SOI07J

每一個(gè)字符串取最后一位：I0O7SJ
既然涉及了字符串的排序，就應(yīng)該想到后綴數(shù)組，我們想想這個(gè)題，要求按照字符串的大小對(duì)各個(gè)排列的字符串進(jìn)行排序。各個(gè)排列的字符串我們完全可以用后綴字符串來表示，再用樣例分析：
JSOI07的后綴字符串有:

JS0I07 SOI07 Oi07 i07 07 7 按照大小排序后： 07 7 i07 JS0I07 Oi07 SOI07

每一列的最后一位為什么沒有？別急，因?yàn)樽址且粋€(gè)環(huán)狀，所以每一列的最后一位也就是第一位的前一位，所以根據(jù)第一位向前推就行
答案還是我們要的I0O7SJ
但是真的就這樣做沒有問題嗎？
當(dāng)s=“bnabn”
我們會(huì)發(fā)現(xiàn)后綴字符串bn會(huì)排在bnabn前面，但是bn對(duì)應(yīng)的是bnbna，應(yīng)該是小于bnabn的，因?yàn)槲覀冇玫暮缶Y字符串，導(dǎo)致缺失的串會(huì)影響結(jié)果，那該怎么辦？
有一個(gè)小技巧，我們將s變成原來的兩倍
s=“bnabn”+“bnabn”=bnabnbnabn
這樣的話，我們?nèi)的后綴字符串就會(huì)包含所有通過s變化的串，但是同時(shí)也會(huì)多出一些部分，會(huì)影響結(jié)果嗎？
并不會(huì)
我們只需要觀察所有sa[i] ≤n的，而對(duì)于這一部分，我們?cè)谇皀位上一定是有序的，后面的一定不會(huì)對(duì)前n位的順序造成影響，這也是我們需要的部分

代碼：

連續(xù)提交三次都未果？洛谷炸了？？

#include <bits/stdc++.h> using namespace std; char ss[1000005]; int c[1000005],Rank[1000005],K,N,M,SA[1000005],Temp[1000005],a[1000005]; void Build(int x) {for (int i=0;i<=x;i++)c[i]=0;for (int i=1;i<=N;i++)c[Rank[Temp[i]]]++;for (int i=1;i<=x;i++)c[i]+=c[i-1];for (int i=N;i>=1;i--)SA[c[Rank[Temp[i]]]--]=Temp[i]; } void BuildSA() {for (int i=1;i<=N;i++)Rank[i]=a[i],Temp[i]=i;Build(M=300);for (int T=1;T<N;T*=2){int p=0;for (int i=N-T+1;i<=N;i++)Temp[++p]=i;for (int i=1;i<=N;i++)if (SA[i]>T) Temp[++p]=SA[i]-T;Build(M=p);swap(Rank,Temp);Rank[SA[1]]=1;p=1;for (int i=2;i<=N;i++){if (Temp[SA[i]]==Temp[SA[i-1]]&&Temp[SA[i]+T]==Temp[SA[i-1]+T]) Rank[SA[i]]=p;else Rank[SA[i]]=++p;}} } int main() {scanf("%s",ss+1);N=strlen(ss+1);for (int i=1;i<=N;i++)a[i]=ss[i],a[i+N]=a[i],ss[i+N]=ss[i];//把這個(gè)字符串復(fù)讀一遍[誤]N*=2;BuildSA();for (int i=1;i<=N;i++)if (SA[i]<=(N/2))cout<<ss[SA[i]+N/2-1];return 0; }

總結(jié)

以上是生活随笔為你收集整理的[JSOI2007]字符加密的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。