【BZOJ1031】[JSOI2007]字符加密Cipher

Description

喜歡鉆研問題的JS同學，最近又迷上了對加密方法的思考。一天，他突然想出了一種他認為是終極的加密辦法 ：把需要加密的信息排成一圈，顯然，它們有很多種不同的讀法。例如下圖，可以讀作：

?

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

Input

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

Output

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

Sample Input

JSOI07

Sample Output

I0O7SJ

HINT

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

題解：后綴數(shù)組第一題~

遇到環(huán)的問題我們肯定要將原字符串復制一遍然后首尾相連，求出sa數(shù)組，然后按著sa的順序一個一個找，如果sa的后綴長度比n大，就輸出答案。

?

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=200010; int ra[maxn],rb[maxn],st[maxn],sa[maxn]; int r[maxn]; char str[maxn]; int n,m; void work() {int *x=ra,*y=rb,i,j,p;for(i=0;i<n;i++) st[x[i]=r[i]]++;for(i=1;i<m;i++) st[i]+=st[i-1];for(i=n-1;i>=0;i--) sa[--st[x[i]]]=i;for(j=1,p=1;p<n;j<<=1,m=p){for(p=0,i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<m;i++) st[i]=0;for(i=0;i<n;i++) st[x[y[i]]]++;for(i=1;i<m;i++) st[i]+=st[i-1];for(i=n-1;i>=0;i--) sa[--st[x[y[i]]]]=y[i];for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;} } int main() {scanf("%s",str);int i;n=strlen(str);for(i=0;i<n;i++) r[i]=r[i+n]=str[i],m=max(r[i]+1,m);n<<=1;r[n++]=0;work();for(i=0;i<n;i++){if(sa[i]<n/2){printf("%c",str[(sa[i]+n/2-1)%(n/2)]);}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/6268364.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1031】[JSOI2007]字符加密Cipher 后缀数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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