[JSOI2007]字符加密
题目大意：
给定一个长度为\(n(n\le10^6)\)的字符串\(s\)。对于\(i\in[1,n)\)，将\(i\)与\(i+1\)之间断开并交换分开的两段可以得到一个新的字符串。将\(s\)和所有这些新的字符串排序后，按顺序输出每个字符串最后一个字符。
思路：
将原串复制两遍构造后缀数组，对于\(sa[i]\)在\(n\)以内的输出\(s_{sa[i]+n-1}\)。若使用倍增+快排构造，时间复杂度\(\mathcal O(n\log^2n)\)。
源代码：
#include<cstdio>#include<cstring>#include<algorithm>const int N=2e5+1;char s[N];int n,k,sa[N],rank[N],tmp[N];inline bool cmp(const int &i,const int &j) { ???if(rank[i]!=rank[j]) return rank[i]<rank[j]; ???const int ri=i+k<n*2?rank[i+k]:-1; ???const int rj=j+k<n*2?rank[j+k]:-1; ???return ri<rj;}inline void suffix_sort() { ???for(register int i=0;i<n*2;i++) { ???????sa[i]=i; ???????rank[i]=s[i]; ???} ???for(k=1;k<n*2;k<<=1) { ???????std::sort(&sa[0],&sa[n*2],cmp); ???????tmp[sa[0]]=0; ???????for(register int i=1;i<n*2;i++) { ???????????tmp[sa[i]]=tmp[sa[i-1]]+!!cmp(sa[i-1],sa[i]); ???????} ???????std::copy(&tmp[0],&tmp[n*2],rank); ???}}int main() { ???scanf("%s",s); ???n=strlen(s); ???std::copy(&s[0],&s[n-1],&s[n]); ???suffix_sort(); ???for(register int i=1;i<n*2;i++) { ???????if(sa[i]<n) putchar(s[sa[i]+n-1]); ???} ???return 0;}[JSOI2007]字符加密
原文地址：https://www.cnblogs.com/skylee03/p/9172956.html