分数: 200 点
问题陈述
在非空字符串上, 左移 将第一个字符移动到字符串的末尾,并且 右移 将最后一个字符移至字符串的开头。
例如,左移 abcde 结果 bcdea,并且两个右移 abcde 结果 deabc.
给你一个非空 S 由小写英文字母组成。进行零次或多次左移和零次或多次右移可以获得的字符串中 S,找到字典顺序最小的字符串和字典顺序最大的字符串。
字典顺序是什么?
简单来说,词典顺序就是单词在词典中列出的顺序。作为更正式的定义,这里是确定不同字符串之间的字典顺序的算法 S 和 T.
下面,让 S_i 表示 i- 第一个字符 S。另外,如果 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
通过移位,我们可以得到四个字符串: aaab, aaba, abaa, baaa。其中按字典顺序最小和最大的是 aaab 和 baaa。
示例输入 2
z
示例输出 2
z z
任何操作序列都会导致 z.
示例输入 3
abracadabra
示例输出 3
aabracadabr racadabraab