项链(字符串最小表示法)
有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！
在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。
达达要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字0至9来标示。
一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： 0-1-2-3 ，它的可能的四种表示是0123、1230、2301、3012。
达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。
也就是说给定两个项链的表示，判断他们是否可能是一条项链。
输入格式
输入文件只有两行，每行一个由字符0至9构成的字符串，描述一个项链的表示（保证项链的长度是相等的）。
输出格式
如果两个对项链的描述不可能代表同一个项链，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。
数据范围
设项链的长度为L，1≤L≤1000000
输入样例：
2234342423
2423223434
输出样例：
Yes
2234342423
字符串的最小表示法：当一个字符串是围成一个圈的形式时，从每个不同的点开始的一个字符串是不一定一样的，存在一个点开始的字符串字典序最小，这就是最小表示法。
比如：一个字符串为 1 2 3 4
此字符串的表示可以为 ：
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4就是这个字符串的最小表示。
怎么求最小表示呢？
- 将字符串复制一遍，加在原字符串后面，处理环的问题。
- 双指针指向当时要比较的两个不同的字符串，依次向后移动，如果不一样或者超过字符串的长度就退出。
- 当退出循环时，假设s[i+k]<s[j+k] ，因为之前的每个字符已经比较过了，可以得出从s[j]到s[j+k]的每一个以它们开始的字符串一定不是最下表示的字符串，反之一样。
因为 i ，j 都不会回溯，所以时间复杂度为O(n)
给出例题代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char str1[N<<1],str2[N<<1];
int n;
int get_min(char *s)//求出这个字符串以什么字符开始，是最小表示的字符串
{
int i=0,j=1;
while(i<n&&j<n)
{
int k=0;
while(s[i+k]==s[j+k]&&k<n) k++;
if(k==n) break;
if(s[i+k]<s[j+k]) j+=k+1;
else i+=k+1;
if(i==j) i++;
}
return min(i,j);
}
int main()
{
cin>>str1>>str2;
n=strlen(str1);
memcpy(str1+n,str1,n);//复制
memcpy(str2+n,str2,n);
int s1=get_min(str1);
int s2=get_min(str2);
str1[s1+n]='\0';
str2[s2+n]='\0';
if(!strcmp(str1+s1,str2+s2)) cout<<"Yes"<<endl<<str1+s1<<endl;
else cout<<"No"<<endl;
return 0;
}
