网站建设应该注意的问题,uc下载的视频禁止自动播放,wordpress关注,做网站图片太大好吗题目描述
喜欢钻研问题的JS 同学#xff0c;最近又迷上了对加密方法的思考。一天#xff0c;他突然想出了一种他认为是终极的加密办法#xff1a;把需要加密的信息排成一圈#xff0c;显然#xff0c;它们有很多种不同的读法。
例如‘JSOI07’#xff0c;可以读作…题目描述
喜欢钻研问题的JS 同学最近又迷上了对加密方法的思考。一天他突然想出了一种他认为是终极的加密办法把需要加密的信息排成一圈显然它们有很多种不同的读法。
例如‘JSOI07’可以读作 JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符I0O7SJ就是加密后的字符串其实这个加密手段实在很容易破解鉴于这是突然想出来的那就^^。 但是如果想加密的字符串实在太长你能写一个程序完成这个任务吗
输入格式 输入文件包含一行欲加密的字符串。注意字符串的内容不一定是字母、数字也可以是符号等。
输出格式 输出一行为加密后的字符串。
输入输出样例 输入 #1复制
JSOI07输出 #1复制
I0O7SJ说明/提示 对于40%的数据字符串的长度不超过10000。
对于100%的数据字符串的长度不超过100000。
题解
样例分析 JSOI07排序后 07JSOI7JSOI0 I07JSO JSOI07 OI07JS SOI07J 每一个字符串取最后一位I0O7SJ 既然涉及了字符串的排序就应该想到后缀数组我们想想这个题要求按照字符串的大小对各个排列的字符串进行排序。各个排列的字符串我们完全可以用后缀字符串来表示再用样例分析 JSOI07的后缀字符串有:
JS0I07
SOI07
Oi07
i07
07
7 按照大小排序后
07
7
i07
JS0I07
Oi07
SOI07每一列的最后一位为什么没有别急因为字符串是一个环状所以每一列的最后一位也就是第一位的前一位所以根据第一位向前推就行 答案还是我们要的I0O7SJ 但是真的就这样做没有问题吗 当s“bnabn” 我们会发现后缀字符串bn会排在bnabn前面但是bn对应的是bnbna应该是小于bnabn的因为我们用的后缀字符串导致缺失的串会影响结果那该怎么办 有一个小技巧我们将s变成原来的两倍 s“bnabn”“bnabn”bnabnbnabn 这样的话我们取s的后缀字符串就会包含所有通过s变化的串但是同时也会多出一些部分会影响结果吗 并不会 我们只需要观察所有sa[i] ≤n的而对于这一部分我们在前n位上一定是有序的后面的一定不会对前n位的顺序造成影响这也是我们需要的部分
代码
连续提交三次都未果洛谷炸了
#include bits/stdc.h
using namespace std;
char ss[1000005];
int c[1000005],Rank[1000005],K,N,M,SA[1000005],Temp[1000005],a[1000005];
void Build(int x)
{for (int i0;ix;i)c[i]0;for (int i1;iN;i)c[Rank[Temp[i]]];for (int i1;ix;i)c[i]c[i-1];for (int iN;i1;i--)SA[c[Rank[Temp[i]]]--]Temp[i];
}
void BuildSA()
{for (int i1;iN;i)Rank[i]a[i],Temp[i]i;Build(M300);for (int T1;TN;T*2){int p0;for (int iN-T1;iN;i)Temp[p]i;for (int i1;iN;i)if (SA[i]T) Temp[p]SA[i]-T;Build(Mp);swap(Rank,Temp);Rank[SA[1]]1;p1;for (int i2;iN;i){if (Temp[SA[i]]Temp[SA[i-1]]Temp[SA[i]T]Temp[SA[i-1]T]) Rank[SA[i]]p;else Rank[SA[i]]p;}}
}
int main()
{scanf(%s,ss1);Nstrlen(ss1);for (int i1;iN;i)a[i]ss[i],a[iN]a[i],ss[iN]ss[i];//把这个字符串复读一遍[误]N*2;BuildSA();for (int i1;iN;i)if (SA[i](N/2))coutss[SA[i]N/2-1];return 0;
}
