侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【最小表示法】项链

GabrielxD
2022-12-29 / 0 评论 / 0 点赞 / 13 阅读 / 655 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

158. 项链


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

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

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

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

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

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

输入格式

输入文件只有两行,每行一个由字符 0099 构成的字符串,描述一个项链的表示(保证项链的长度是相等的)。

输出格式

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

数据范围

设项链的长度为 LL1L10000001 \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;
}
0

评论区