M_sea

洛谷4051 [JSOI2007]字符加密
LuoguBZOJ分析把原串赋值一遍接在原串上,这样子每个写出的字符串都变成了某一个后缀的长度为$n$的前缀。跑一...
扫描右侧二维码阅读全文
14
2019/01

洛谷4051 [JSOI2007]字符加密

Luogu

BZOJ

分析

把原串赋值一遍接在原串上,这样子每个写出的字符串都变成了某一个后缀的长度为$n$的前缀。

跑一遍后缀排序直接输出就行啦。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

char s[N];
int sa[N],rank[N];
int x[N],y[N],z[N];

inline void Suffix_Sort() {
    int m=255,n=strlen(s+1);
    for (re int i=1;i<=n;++i) ++z[x[i]=s[i]];
    for (re int i=2;i<=m;++i) z[i]+=z[i-1];
    for (re int i=n;i>=1;--i) sa[z[x[i]]--]=i;
    for (re int k=1;k<=n;k<<=1) {
        int p=0;
        for (re int i=n-k+1;i<=n;++i) y[++p]=i;
        for (re int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
        for (re int i=1;i<=m;++i) z[i]=0;
        for (re int i=1;i<=n;++i) ++z[x[i]];
        for (re int i=2;i<=m;++i) z[i]+=z[i-1];
        for (re int i=n;i>=1;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        x[sa[1]]=1,p=1;
        for (re int i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p:++p;
        if (p==n) break; m=p;
    }
}

int main() {
    scanf("%s",s+1); int n=strlen(s+1);
    for (re int i=1;i<=n;++i) s[i+n]=s[i];
    Suffix_Sort();
    for (re int i=1;i<=(n<<1);++i)
        if (sa[i]<=n) putchar(s[sa[i]+n-1]);
    putchar('\n');
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 29 PM

发表评论