【板子】字符串最小表示法

//lg p1368
//Copyright yeyou26
#include<bits/stdc++.h>
using namespace std;

long long a[600005];
int n;

void init();
void solve()
{
    int i=1,j=2,k=0;
    while(i<=n && j<=n)
    {
        k=0;
        while(a[i+k]==a[j+k] && k<n) k++;
        if(a[i+k]>a[j+k]) i=i+k+1;
        else j=j+k+1;
        if(k==n) goto loop;
        if(i==j) j++;
    }
    loop :
    int ans=min(i,j);
    for(int p=1;p<=n;p++)
    {
        printf("%lld ",a[ans+p-1]);
    }
}

int main()
{
    freopen("working.in","r",stdin);
    freopen("working.out","w",stdout);
    init();
    solve();
    return 0;
}

//Function Implementation

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        long long x;
        scanf("%lld",&x);
        a[i]=a[i+n]=x;
    }
}