AT_abc223_b [ABC223B] String Shifting

题目描述

对于一个非空字符串，将首字母移动到末尾的操作称为左移，将末尾字母移动到首位的操作称为右移。

例如，对 abcde 进行 $1$ 次左移后得到 bcdea，进行 $2$ 次右移后得到 deabc。

给定一个仅由小写英文字母组成的非空字符串 $S$。请你求出对 $S$ 进行任意次数（可以为 $0$ 次）的左移或右移操作后能得到的所有字符串中，按字典序最小和最大的字符串。

什么是字典序？字典序简单来说就是“单词在字典中出现的顺序”。更严格地说，判断由小写英文字母组成的两个不同字符串 $S,\ T$ 的大小关系的算法如下：

记 $S$ 的第 $i$ 个字符为 $S_i$。若 $S$ 在字典序上小于 $T$，记作 $S < T$，大于则记作 $S > T$。

1. 取 $S,\ T$ 中较短的字符串长度为 $L$。依次比较 $i=1,2,\dots,L$ 时 $S_i$ 和 $T_i$ 是否相等。
2. 如果存在 $S_i \neq T_i$，则取最小的此类 $i$ 为 $j$，比较 $S_j$ 和 $T_j$。若 $S_j$ 的字母序小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。
3. 如果所有 $S_i = T_i$，则比较 $S$ 和 $T$ 的长度，短的为小，长的为大，算法结束。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

输出 $2$ 行。第一行为对 $S$ 进行任意次数左移或右移操作后能得到的所有字符串中字典序最小的字符串 $S_{\min}$，第二行为字典序最大的字符串 $S_{\max}$。

输入输出样例 #1

输入 #1

aaba

输出 #1

aaab
baaa

输入输出样例 #2

输入 #2

z

输出 #2

z
z

输入输出样例 #3

输入 #3

abracadabra

输出 #3

aabracadabr
racadabraab

说明/提示

限制条件

• $S$ 仅由小写英文字母组成。
• $S$ 的长度为 $1$ 到 $1000$。

样例解释 1

通过操作，可以得到 aaab、aaba、abaa、baaa 共 $4$ 种字符串。其中字典序最小和最大分别为 aaab 和 baaa。

样例解释 2

无论如何操作，得到的字符串都只有 z。

由 ChatGPT 4.1 翻译