当前位置: 代码迷 >> 综合 >> P4051 [JSOI2007]字符加密 (后缀数组sa[])
  详细解决方案

P4051 [JSOI2007]字符加密 (后缀数组sa[])

热度:92   发布时间:2024-02-10 02:32:57.0

题意:

喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法
:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:

在这里插入图片描述

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0
把它们按照字符串的大小排序:07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J
读出最后一列字符:I0O7SJ,就是加密后的字符串
(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。
但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

数据范围:字符串长度<=1e5

解法:

这道题实际上是在环上对每个点作为起点的串进行排序,
序列和环容易想到破环成链,具体做法就是复制一遍序列接在后面.

题目中的每个串一定都是新串的某个后缀的前缀
题目中的n个串就是新串中串[1,n]的后缀的长度为n的前缀
对新串构造后缀数组,sa[1]到sa[n]就是题目的排序结果
那么s[sa[i]+n-1]就是末尾字符

ps:
这种方法似乎可以用来求字符串的最小表示法(第k小表示法?)

code:

#include<bits/stdc++.h>
using namespace std;
const int maxm=1e5+5;
struct SA{static const int N=1e6+5;char s[N];int sa[N],rk[N],oldrk[N<<1],id[N],px[N],cnt[N];int n;bool cmp(int x,int y,int w){return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];}void getSA(){int m=300;//字符集大小int i,p,w;for(i=1;i<=n;i++)cnt[rk[i]=s[i]]++;for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];for(i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;//for(w=1;w<n;w<<=1,m=p){for(p=0,i=n;i>n-w;i--)id[++p]=i;for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;memset(cnt,0,sizeof cnt);for(i=1;i<=n;i++)cnt[px[i]=rk[id[i]]]++;for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];for(i=n;i>=1;i--)sa[cnt[px[i]]--]=id[i];memcpy(oldrk,rk,sizeof rk);for(p=0,i=1;i<=n;i++){rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;}}//
// for(int i=1;i<=n;i++)printf("%d ",sa[i]);
// puts("");}
}sa;
signed main(){scanf("%s",sa.s+1);sa.n=strlen(sa.s+1);//复制for(int i=1;i<=sa.n;i++)sa.s[i+sa.n]=sa.s[i];sa.n*=2;//sa.getSA();for(int i=1;i<=sa.n;i++){if(sa.sa[i]<=sa.n/2){printf("%c",sa.s[sa.sa[i]+sa.n/2-1]);}}return 0;
}