bzoj1398 Vijos1382寻找主人 Necklace

题目

最小表示法，模板。

果然权限号板子多啊。

背过吧2333

#include<bits/stdc++.h>
#define N 2000000
using namespace std;
char a[N+],b[N+];
char c[N+],d[N+];
int n,m1,m2;
inline int get_M(char *tmp,int len)
{
    int i=,j=,k=;
    while(i<len&&j<len&&k<len)
    {
        int cmp=tmp[(i+k)%len]-tmp[(j+k)%len];
        if(cmp==)k++;
        else
        {
            if(cmp>)i+=k+;
            else j+=k+;
            if(i==j)j++;
            k=;
        }
    }
    return min(i,j);
}
int main()
{
    freopen("in.txt","r",stdin);
    scanf("%s%s",a,b);
    n=strlen(a);
    m1=get_M(a,n);
    m2=get_M(b,n);
    for(int i=;i<n;i++)c[i]=a[(i+m1)%n],d[i]=b[(i+m2)%n];
    for(int i=;i<n;i++)
        if(c[i]!=d[i])return printf("No\n"),;
    printf("Yes\n");
    for(int i=;i<n;i++)printf("%c",c[i]);
    printf("\n");
    return ;
}