bzoj1031 [JSOI2007]字元加密Cipher

bzoj1031 [JSOI2007]字元加密Cipher
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

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;
}

相關文章

程式語言 最新文章