158. 项链【字符串的最小表示】

有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！

在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。

达达要求每个人都写了一段关于自己项链的描述：项链上的宝石用数字0至9来标示。

一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： 0-1-2-3 ，它的可能的四种表示是0123、1230、2301、3012。

达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。

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

输入格式

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

输出格式

如果两个对项链的描述不可能代表同一个项链，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。

数据范围

设项链的长度为L，1≤L≤1000000<?XML:NAMESPACE PREFIX = "[default] http://www.w3.org/1998/Math/MathML" NS = "http://www.w3.org/1998/Math/MathML" />1≤L≤1000000

输入样例：

2234342423
2423223434

输出样例：

Yes
2234342423

最小表示法：

1.初始化 i= 1, j = 2.

2.通过直接向后扫描，比较s[i],s[j]两个同构字符串的大小。

（1）如果扫描了n个字符任然相等，说明字符串s是由一个字符构成。
（2）如果在i+k与j+k处发现不相等：
若s[i+k] > s[j+k]，则邻 i = i + k + 1 ,若 i = j ，则 i++;
若s[j+k] > s[i+k]，则邻 j = j + k + 1 ,若 i = j ，则 j++;

3.若 j > n，则s[i ~(i + n)]是最小表示，若i > n,则s[j~(j+n)]是最小表示；否则重复2

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string s, s1;
    cin >> s >> s1;
    s = s + s;
    int n = s1.size();
    if(s.find(s1) != string::npos){
        puts("Yes");
        int i = 0, j = 1, k;
        while(i < n && j < n) {
            for(k = 0; k < n && s[i + k] == s[j + k]; k ++);
            if(k == n - 1) break;
            if(s[i+k] > s[j+k]) {
                i = i + k + 1;
                if(i == j) i += 1;
            }
            else {
                j = j + k + 1;
                if(i == j) j += 1;
            }
        }
        int ans = min(i, j);
        for(int i = ans; i < ans + n; ++ i) cout << s[i];
    }
    else puts("No");
}