形式化题目

给定两个长度相同（$L \leqslant 10^6$）、由数字 0–9 组成的字符串 $A$ 和 $B$。规定字符串 $S$ 的"旋转"是把 $S$ 的某个后缀移到最前面得到的结果，例如 0123 的四个旋转是 0123、1230、2301、3012。

判断 $B$ 是否是 $A$ 的某个旋转（注意项链不能翻转，即不允许逆序）。若不可能，输出 No；否则第一行输出 Yes，第二行输出 $A$ 的所有旋转中字典序最小的一个。

样例

输入：

1
22234342423
2423223434

输出：

1
2Yes
2234342423

2423223434 正是 2234342423 把末尾 4 位挪到最前得到的旋转，因此是同一条项链；它的最小表示就是输入中的第一个串。

正解

思路

朴素做法：枚举 $A$ 的 $L$ 个起点，每个起点把整圈拼出来与 $B$ 比较，任一次相等即 Yes；最小表示则是 $L$ 个旋转里字典序最小的那个。单次比较要 $O(L)$，总复杂度 $O(L^2)$，在 $L = 10^6$ 时约 $10^{12}$ 次字符比较，必然超时。瓶颈在于：候选起点两两之间的比较大量重复，前一次比较的信息被完全丢弃。

关键观察：要判断"同一条项链"，其实不需要拿 $B$ 来逐个比对——两条项链相同当且仅当它们的最小表示（字典序最小的旋转）相同。最小表示是一个"规范形"：同一项链的所有描述旋转后得到的最小表示彼此相等，不同项链的最小表示必然不同（两个不同的旋转不可能同为最小）。于是问题归为：对 $A$、$B$ 各求一次最小表示，比较即可。

最小表示法（双指针跳段）：用两个起点指针 $i, j$（初始 $0, 1$）在环上"赛跑"，$k$ 记录当前两个候选起点已连续匹配的长度：

• 若 $s[i+k] = s[j+k]$，说明两位打平，$k$ 加一继续比下一位；
• 若 $s[i+k] < s[j+k]$，则起点 $j$ 落败。而且不止 $j$：对任意 $0 \leqslant t \leqslant k$，起点 $j+t$ 与起点 $i+t$ 的前 $k-t$ 位完全相同，却在第 $k-t$ 位更大，所以 $j, j+1, \ldots, j+k$ 整段都不可能成为最小表示的起点，直接令 $j \mathrel{+}= k+1$；
• $s[i+k] > s[j+k]$ 时对称地令 $i \mathrel{+}= k+1$。

每次失配至少有一方前进 $k+1$ 步，且被跳过的起点都被证明不可能最优；$i$ 与 $j$ 重合时把 $j$ 后移一位保持两指针错开。指针总共只走 $O(L)$ 步，即使中间某次匹配了很长一段（$k$ 很大），代价也记在被淘汰一方的"跳段"里，均摊 $O(L)$。任一指针越过 $n$ 时，剩下的那个起点就是最小表示的起点。

下表用样例中的串 22343424 模拟跳段过程，展示落败方如何整段或逐个被淘汰：

第 2 步中起点 $1$ 与起点 $0$ 的前 2 位对局里，$k{+}1{=}2$ 一次淘汰了 $j{=}1$（以及它与 $i$ 之间隐含的候选），第 5 步 $j$ 越过 $n$ 后起点 $0$ 胜出，正是 22343424 的最小表示。全程每个起点至多被淘汰一次，故为线性。

注意 $L = 1$ 时初始 $j = 1$ 已越界，循环条件直接不成立，最小表示就是原串，无需特判。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39import sys

def min_rotation(s: str) -> str:
    """最小表示法（Lyndon / Booth 思想）：返回循环串 s 的字典序最小旋转。

    i, j 是两个候选起点，k 是当前匹配长度：
    - s[i+k] == s[j+k]：k 继续延伸；
    - s[i+k] < s[j+k]：j..j+k 都不可能成为更优起点，j 跳到 j+k+1；
    - s[i+k] > s[j+k]：同理 i 跳到 i+k+1。
    跳跃保证失败者整体后移，均摊 O(L)。
    """
    s = list(map(ord, s))
    n = len(s)
    i, j, k = 0, 1, 0
    while k < n and i < n and j < n:
        d = s[(i + k) % n] - s[(j + k) % n]
        if d == 0:
            k += 1
        else:
            if d > 0:
                i += k + 1  # i..i+k 全部落败，一起跳过
            else:
                j += k + 1
            if i == j:
                j += 1  # 两指针不能重合
            k = 0
    return ''.join(chr(c) for c in s[min(i, j):] + s[:min(i, j)])

def main() -> None:
    data = iter(sys.stdin.buffer.read().split())
    a, b = next(data).decode(), next(data).decode()
    ma = min_rotation(a)  # 两串相等当且仅当最小表示相等
    if ma == min_rotation(b):
        print('Yes')
        print(ma)
    else:
        print('No')

main()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:42
 * update_at: 2026-10-06 16:42
 */
#include <cstdio>
#include <cstring>

const int MAXL = 1000005; // 项链长度上限 10^6，多留一点空间

char a[MAXL]; // 第一条项链的描述
char b[MAXL]; // 第二条项链的描述

// 求循环串 s（长度为 n）的字典序最小旋转的起点下标。
// i、j 是两个候选起点，k 是当前已连续匹配的长度；
// 失配时落败的一方连同它后面的 k 个候选一起被淘汰，跳到 k+1 步之后，
// 每个起点至多被淘汰一次，因此均摊 O(n)。
int min_rotation(char *s, int n) {
    int i = 0;
    int j = 1;
    int k = 0;
    while (k < n && i < n && j < n) {
        char ci = s[(i + k) % n];
        char cj = s[(j + k) % n];
        if (ci == cj) {
            k++;
        } else {
            if (ci > cj) {
                i += k + 1; // 起点 i..i+k 全部落败，整体跳过
            } else {
                j += k + 1; // 起点 j..j+k 全部落败，整体跳过
            }
            if (i == j) {
                j++; // 两指针重合时错开
            }
            k = 0;
        }
    }
    return i < j ? i : j;
}

int main() {
    scanf("%s %s", a, b);
    int n = strlen(a);
    int pa = min_rotation(a, n);
    int pb = min_rotation(b, n);
    // 两条项链相同当且仅当它们的最小表示相同。
    int same = 1;
    for (int t = 0; t < n; t++) {
        if (a[(pa + t) % n] != b[(pb + t) % n]) {
            same = 0;
            break;
        }
    }
    if (same) {
        printf("Yes\n");
        for (int t = 0; t < n; t++) {
            putchar(a[(pa + t) % n]);
        }
        putchar('\n');
    } else {
        printf("No\n");
    }
    return 0;
}

复杂度

• 时间：两个指针在环上至多各前进 $O(L)$ 步，失配时跳过的每一步都对应一个被永久淘汰的起点，总均摊 $O(L)$；对 $A$、$B$ 各做一次再加一次字符串比较，仍为 $O(L)$，$L \leqslant 10^6$ 轻松通过。
• 空间：把字符串转成码点列表比较以便逐位取模访问，$O(L)$。

总结

• 判断两个循环串描述是否同构，不必逐旋转比对：各自求最小表示（规范形）再比较即可，这一步把"与 $B$ 匹配"降成"与规范形匹配"。
• 最小表示法用双指针 + 失配跳段：失配时落败方连同其后 $k$ 个起点一起被证明不可能最优，一次跳 $k+1$ 步，均摊线性，远优于 $O(L^2)$ 的朴素枚举。
• 实现要点：环上访问用取模；$i = j$ 时强制错开；$L = 1$ 由循环条件自然覆盖。
• 同类模型：求循环串的最大表示（比较方向取反）、循环同构判断（uvwu 拼接后找单次出现）、以及 Lyndon 分解，都建立在同一套双指针跳段思想上。