BZOJ-2882/1398: 工艺

Description

求一个字符串字典序最小的循环串。len<=10^6

最小表示法，时间复杂度O(len)
2882:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char f=1,ch=nc();
    while(!isdigit(ch)){if(ch=='-') f=0; ch=nc();}
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return f ? re : -re;
}
int n,s[301000];
int main()
{
    n=read();
    int i;
    for(i=0;i<n;++i) s[i]=read();
    int j,k;
    i=0; j=1; k=0;
    while(i<n&&j<n)
    {
        while(k<n)
        {
            if(s[(i+k)%n]!=s[(j+k)%n]) break;
            else ++k;
        }
        if(k==n) break;
        (s[(i+k)%n]<s[(j+k)%n]) ? j+=k+1 : i+=k+1;
        k=0; if(i==j) j++;
    }
    i=min(i,j);
    for(k=0;k<n;++k) printf("%d%c",s[(i+k)%n],k==(n-1) ? '\n' : ' ');
    return 0;
}

1398:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
char s1[1001000],s2[1001000];
int n,a1,a2;
int calc(char *s)
{
    int i=0,j=1,k=0;
    while(i<n&&j<n)
    {
        k=0;
        while(k<n)
        {
            if(s[(i+k)%n]!=s[(j+k)%n]) break;
            else ++k;
        }
        if(k==n) break;
        (s[(i+k)%n]<s[(j+k)%n]) ? j+=k+1 : i+=k+1;
        if(i==j) ++j;
    }
    return (i<j) ? i : j;
}
int main()
{
    scanf("%s%s",s1,s2);
    n=strlen(s1);
    a1=calc(s1); a2=calc(s2);
    for(int i=0;i<n;++i)
    {
        if(s1[(a1+i)%n]!=s2[(a2+i)%n])
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i=0;i<n;++i) printf("%c",s1[(a1+i)%n]);
    return 0;
}