COJ883 工艺品

试题描述

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 ;

}