配点 : 100 点
問題文
N 字符或字符串
按此顺序连接的 X_1, X_2, \dots, X_N 字符串是
写为 X_1 + X_2 + \cdots + X_N 。
为字符串定义汉堡、整个汉堡和半个汉堡,如下所示。这个定义与问题E相同。
- Burger 是一个完整汉堡的字符串和一个半汉堡的字符串。
- 整个汉堡就是汉堡。 A 某些字符 对于 c , 可写为c + A + c 的字符串和空字符串
- 半个汉堡是不是空的汉堡。 在可以写成 A、B , 可写为A + B 的字符串中,不全是汉堡的字符串
例如,abba 呀
诸如 abbcca 都是汉堡,aabb 呀
诸如 abbacc 是半个汉堡,abbcbbc 呀
诸如 ababa 不是汉堡。
小写英文字母组成的字符串
对于 S ,
一串小写字母,S + T 都是汉堡。
当 T 存在时,|T| 是最小值
请输出 T 中按字典顺序最小的一个。像那样
如果 T 不存在, -1 。
只需选择 2 和 9 即可
什么是字典顺序?
文字列 S = S_1S_2 \cdots S_{|S|} 是一个字符串 来自 T = T_1T_2 \cdots T_{|T|} 捻 按字典顺序最小 表示以下 1. 或 2. 成立。在这里,|S|, |T| 分别是 表示 S,T 的长度。- 1. |S| < |T| 和 满足 S = S_1S_2 \cdots S_{|S|} = T_1T_2 \cdots T_{|S|}。
- 2. 整数 1 \leq i \leq \min\{|S|, |T|\} 存在并且以下内容 2 两者都成立。 按字母顺序排列,它小于
- S = S_1S_2 \cdots S_{i-1} = T_1T_2 \cdots T_{i-1}
- S_i 是 在 T_i 。
制約
- 1 \leq |S| \leq 200{,}000
- S 是一串小写字母
小課題
-
( 1 点) S 是 它仅由
a和b变为|S| \leq 10 的字符串 -
( 99 点)无附加约束
入力
输入是按以下格式从标准输入给出的。
S
出力
答案是 1 行。
入力例 1
abcca
出力例 1
aba
T = aba 然后,S+T = abccaaba 都是汉堡。
满足条件
除了 T 是
它仅由 aba 之外还有其他可能性,2 没有什么比一个角色更重要的了,3 是一个字符 T 中,按字典顺序最小的是
输出 aba ,所以
它可以是aba 。
该测试用例不满足子任务 1 的约束。 如果
入力例 2
abba
出力例 2
T 是空字符串,S+T = abba 都是汉堡。
该测试用例满足子任务 1 的约束。