BZOJ 1398: Vijos1382寻找主人 Necklace（最小表示法）

Description

给定两个项链的表示，判断他们是否可能是一条项链。

Input

输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

Output

如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’
第二行输出该项链的字典序最小的表示。 设L = 项链长度，L <= 1000000。

---

题解：
题目已经说了字典序最小的表示了，那我们直接上最小表示法就好了，记下两个位置，循环判断输出，没什么难度

---

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define int long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
const int MAXN = 1e6+50;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
char s1[MAXN],s2[MAXN]; int len;
inline int solve(char *s){
	int i=0,j=1;
	while(i<len && j<len){
		int k=0;
		while(s[(i+k)%len]==s[(j+k)%len]) k++;
		if(k==len) break;
		if(s[(i+k)%len]>s[(j+k)%len]) i+=k+1;
		else j+=k+1;
		if(i==j) j++;
	}
	return min(i,j);
}
inline bool check(int p1,int p2){
	int k=0;
	while(k<len){
		if(s1[(p1+k)%len]!=s2[(p2+k)%len]) return false;
		k++;
	}
	return true;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
	scanf("%s%s",s1,s2); len=strlen(s1);
	int p1=solve(s1),p2=solve(s2);
	if(!check(p1,p2)) puts("No");
	else{
		puts("Yes");
		for(int i=0;i<len;i++) putchar(s1[(p1+i)%len]);
	}
    return 0;
}