102231: [AtCoder]ABC223 B - String Shifting
Description
Score : $200$ points
Problem Statement
On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.
For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.
You are given a non-empty $S$ consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on $S$, find the lexicographically smallest string and the lexicographically largest string.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings $S$ and $T$.
Below, let $S_i$ denote the $i$-th character of $S$. Also, if $S$ is lexicographically smaller than $T$, we will denote that fact as $S \lt T$; if $S$ is lexicographically larger than $T$, we will denote that fact as $S \gt T$.
- Let $L$ be the smaller of the lengths of $S$ and $T$. For each $i=1,2,\dots,L$, we check whether $S_i$ and $T_i$ are the same.
- If there is an $i$ such that $S_i \neq T_i$, let $j$ be the smallest such $i$. Then, we compare $S_j$ and $T_j$. If $S_j$ comes earlier than $T_j$ in alphabetical order, we determine that $S \lt T$ and quit; if $S_j$ comes later than $T_j$, we determine that $S \gt T$ and quit.
- If there is no $i$ such that $S_i \neq T_i$, we compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we determine that $S \lt T$ and quit; if $S$ is longer than $T$, we determine that $S \gt T$ and quit.
Constraints
- $S$ consists of lowercase English letters.
- The length of $S$ is between $1$ and $1000$ (inclusive).
Input
Input is given from Standard Input in the following format:
$S$
Output
Print two lines. The first line should contain $S_{\min}$, and the second line should contain $S_{\max}$. Here, $S_{\min}$ and $S_{\max}$ are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on $S$.
Sample Input 1
aaba
Sample Output 1
aaab baaa
By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.
Sample Input 2
z
Sample Output 2
z z
Any sequence of operations results in z.
Sample Input 3
abracadabra
Sample Output 3
aabracadabr racadabraab
Input
题意翻译
对于非空字符串，将第一个字符移到末尾的操作称为**左移**，将末尾字符移到开头的操作称为**右移**。请在将输入的字符串 $s$ 左移若干次和右移若干次的字符串中找到字典序最小和最大的字符串并依次输出。Output
分数：$200$分
问题描述
在一个非空字符串上，左移将第一个字符移动到字符串的末尾，而右移将最后一个字符移动到字符串的开头。
例如，对abcde进行左移操作结果为bcdea，对abcde进行两次右移操作结果为deabc。
给你一个由小写英文字母组成的非空字符串$S$。在对$S$进行零次或多次左移和零次或多次右移操作后，找到字典序最小的字符串和字典序最大的字符串。
什么是字典序？
简单来说，字典序就是字典中单词的排列顺序。更正式的定义如下，用于确定不同字符串$S$和$T$之间的字典序。
下面，令$S_i$表示$S$的第$i$个字符。此外，如果$S$的字典序小于$T$，我们将表示为$S \lt T$；如果$S$的字典序大于$T$，我们将表示为$S \gt T$。
- 让$L$为$S$和$T$长度中较小的一个。对于每个$i=1,2,\dots,L$，我们检查$S_i$和$T_i$是否相同。
- 如果存在一个$i$使得$S_i \neq T_i$，让$j$为这样的最小$i$。然后，我们比较$S_j$和$T_j$。如果$S_j$在字母顺序上早于$T_j$，我们确定$S \lt T$并退出；如果$S_j$晚于$T_j$，我们确定$S \gt T$并退出。
- 如果不存在这样的$i$使得$S_i \neq T_i$，我们比较$S$和$T$的长度。如果$S$比$T$短，我们确定$S \lt T$并退出；如果$S$比$T$长，我们确定$S \gt T$并退出。
约束条件
- $S$由小写英文字母组成。
- $S$的长度在$1$到$1000$（含）之间。
输入
输入从标准输入中给出，格式如下：
$S$
输出
打印两行。第一行应包含$S_{\min}$，第二行应包含$S_{\max}$。这里，$S_{\min}$和$S_{\max}$分别是通过对$S$进行零次或多次左移和零次或多次右移操作获得的字典序最小和最大的字符串。
样例输入 1
aaba
样例输出 1
aaab baaa
通过进行移