|
试题描述
|
|
LZJ和XJR是一对好朋友。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。
|
|
输入
|
|
第二行为一个字符串S，S的第i位就是该位置方块的瑕疵值。
|
|
输出
|
|
输出一个字符串，代表最美观工艺品从左到右瑕疵度的值。
|
|
输入示例
|
|
0101321001
|
|
输出示例
|
|
0010101321
|
|
其他说明
|
|
1<=|S|<=100000
|
字符串最小表示
用SAM的做法是这样的，将原串重复一次构造SAM，按字典序贪心走|S|次即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int l[maxn],fa[maxn],to[maxn][],last=,cnt=;
void extend(int c) {
int p,q,np,nq;
p=last;l[np=last=++cnt]=l[p]+;
for(;!to[p][c];p=fa[p]) to[p][c]=np;
if(!p) fa[np]=;
else {
q=to[p][c];
if(l[p]+==l[q]) fa[np]=q;
else {
l[nq=++cnt]=l[p]+;
memcpy(to[nq],to[q],sizeof(to[nq]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;to[p][c]==q;p=fa[p]) to[p][c]=nq;
}
}
}
char s[maxn];
int main() {
scanf("%s",s);int n=strlen(s),p=;
rep(,n-) extend(s[i]-'');
rep(,n-) extend(s[i]-'');
while(n--) {
rep(,) if(to[p][i]) {putchar(i+'');p=to[p][i];break;}
}
return ;
}