项链表示匹配问题

题目描述

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

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

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

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

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入样例

2234342423
2423223434

输出样例

Yes
2234342423

限制条件

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

时间限制

1秒

空间限制

64MB

问题分析

这是一个环形字符串匹配问题。给定两个字符串 $s1$ 和 $s2$，长度都为 $L$，判断它们是否表示同一个环形项链。

关键点：

1. 项链是环形的，可以从任意位置开始表示
2. 项链不会翻转，只能顺时针方向
3. 需要找到字典序最小的表示

解决方案：

方法1：字符串最小表示法 对于每个字符串，找到其所有循环同构中字典序最小的表示（最小表示）。

• 如果两个字符串的最小表示相同，则它们是同一个项链
• 否则，不是同一个项链

算法步骤：

1. 检查两个字符串长度是否相等（题目已保证）
2. 对每个字符串求最小表示：
   • 复制字符串一次：s = s + s
   • 使用双指针法在 $O(n)$ 时间内找到最小表示的起始位置
3. 比较两个最小表示是否相等
4. 输出结果

最小表示法算法（双指针）：

int n = s.length();
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
    char a = s[(i + k) % n];
    char b = s[(j + k) % n];
    if (a == b) {
        k++;
    } else {
        if (a > b) i += k + 1;
        else j += k + 1;
        if (i == j) i++;
        k = 0;
    }
}
int start = min(i, j);
// 最小表示为 s[start...(start+n-1) mod n]

样例解释

输入：

s1 = "2234342423"
s2 = "2423223434"

求各自的最小表示：

• s1的最小表示："2234342423"（从位置0开始）
• s2的最小表示："2234342423"（从某个位置开始旋转得到）

由于两个最小表示相同，所以是同一个项链，输出：

Yes
2234342423

时间复杂度

• 求最小表示：$O(L)$
• 总复杂度：$O(L)$，对于 $L \le 10^6$ 可行

空间复杂度

• 需要存储两个字符串：$O(L)$
• 求最小表示时可能需要复制字符串：$O(L)$
• 总空间：$O(L)$