Luogu P4051 [JSOI2007]字符加密

题意：给出一个字符串 \(S\) ，将 \(S\) 所有的循环同构串按字典序排序，按顺序输出排序后每个串的首字符。

\(SA\) 把串复制一倍拼在后面，然后进行后缀排序即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
  register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
  do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=200010;
int n,l,sa[N],x[N],y[N],c[N];
char s[N];
inline void pre() {
  R m=122;
  for(R i=1;i<=n;++i) ++c[x[i]=s[i]];
  for(R i=1;i<=m;++i) c[i]+=c[i-1];
  for(R i=n;i;--i) sa[c[x[i]]--]=i;
  for(R t=1,top=0;top<n;m=top,t<<=1) {
    top=0;
    for(R i=n-t+1;i<=n;++i) y[++top]=i;
    for(R i=1;i<=n;++i) if(sa[i]>t) y[++top]=sa[i]-t;
    memset(c,0,(m+1)<<2);
    for(R i=1;i<=n;++i) ++c[x[i]];
    for(R i=1;i<=m;++i) c[i]+=c[i-1];
    for(R i=n;i;--i) sa[c[x[y[i]]]--]=y[i];
    swap(x,y),x[sa[1]]=top=1;
    for(R i=2;i<=n;++i)
      x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+t]==y[sa[i-1]+t])?top:++top;
  }
}
inline void main() {
  scanf("%s",s+1),n=strlen(s+1);
  memmove(s+n+1,s+1,n),l=n,n<<=1;
  pre(); for(R i=1;i<=n;++i) 
    if(sa[i]<=l) putchar(s[sa[i]+l-1]);
} 
} signed main() {Luitaryi::main(); return 0;}

\(SAM\) ...没必要吧。

2020.01.09

Luogu P4051 [JSOI2007]字符加密

原文：https://www.cnblogs.com/Jackpei/p/12177294.html