【最小表示法】项链

题目

158. 项链

---

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

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

设项链的长度为 $L$ ， $1 \le L \le 1000000$

输入样例：

2234342423
2423223434

输出样例：

Yes
2234342423

解题

方法一：字符串的最小表示法

思路

如果两个字符串的最小表示法相同，那么它们循环同构，详见：最小表示法 - OI Wiki。

代码

#include <iostream>

using namespace std;

void min_str(string& s) {
    int n = s.size(), k = 0, i = 0, j = 1;
    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) ++k;
        else {
            if (s[(i + k) % n] > s[(j + k) % n]) i += k + 1;
            else j += k + 1;
            if (i == j) ++i;
            k = 0;
        }
    }
    i = min(i, j);
    s += s.substr(0, i);
    s.erase(0, i);
}

int main() {
    string a, b;
    getline(cin, a);
    getline(cin, b);
    min_str(a);
    min_str(b);
    if (a == b) {
        puts("Yes");
        printf("%s\n", a.c_str());
    } else puts("No");
    
    return 0;
}