p4051 [JSOI2007]字符加密

传送门

分析

将字符串复制一遍然后直接求sa即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

char s[];

int n,m=,rk[],sa[],tax[],tp[],h[],height[];

inline void qsort(){

    for(int i=;i<=m;i++)tax[i]=;

    for(int i=;i<=n;i++)tax[rk[i]]++;

    for(int i=;i<=m;i++)tax[i]+=tax[i-];

    for(int i=n;i>;i--)sa[tax[rk[tp[i]]]--]=tp[i];

}

inline void work(){

    for(int i=;i<=n;i++)rk[i]=s[i]-''+,tp[i]=i;qsort();

    for(int w=,p=;p<n;m=p,w<<=){

      p=;for(int i=;i<=w;i++)tp[++p]=n-w+i;

      for(int i=;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;

      qsort();swap(rk,tp);rk[sa[]]=p=;

      for(int i=;i<=n;i++)rk[sa[i]]=(tp[sa[i-]]==tp[sa[i]]&&tp[sa[i-]+w]==tp[sa[i]+w])?p:++p;

    }

    for(int i=;i<=n;i++)rk[sa[i]]=i;h[]=;

    for(int i=;i<=n;i++){

      h[i]=max(h[i-]-,);

      while(i+h[i]<=n&&sa[rk[i]-]<=n&&s[i+h[i]]==s[sa[rk[i]-]+h[i]])h[i]++;

    }

    for(int i=;i<=n;i++)height[i]=h[sa[i]];

}

int main(){

    scanf("%s",s+);n=strlen(s+);for(int i=;i<=n;i++)s[i+n]=s[i];

    n<<=;work();for(int i=;i<=n;i++)if(sa[i]<=n/)cout<<s[sa[i]+n/-];

    return ;

}