求循环排列的排名,直接把原串复制一遍接在后面做后缀数组就行了.
CODE
#include
using namespace std;
char cb[1#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1templateinline void read(T &res) {
char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 200005;
char s[MAXN];
int x[MAXN], y[MAXN], c[MAXN], rk[MAXN], sa[MAXN];
inline void Get_Sa(int n, int m) {
for(int i = 1; i for(int i = 1; i for(int i = 2; i for(int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for(int k = 1; k int p = 0;
for(int i = n-k+1; i for(int i = 1; i k) y[++p] = sa[i]-k;
for(int i = 1; i for(int i = 1; i for(int i = 2; i for(int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
x[sa[1]] = p = 1;
for(int i = 2; i x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? p : ++p;
if((m=p) == n) break;
}
for(int i = 1; i }
int n;
int main() {
scanf("%s", s+1); n = strlen(s+1);
for(int i = 1; i Get_Sa(n for(int i = 1; i putchar(s[sa[i]>1?sa[i]-1:n]);
}