bzoj1031 [JSOI2007]字元加密Cipher

bzoj1031 [JSOI2007]字元加密Cipher

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