← 返回题目列表

AtCoder · oupc2023_day1_d

D. 韩汉堡

中文机器翻译题面 查看原题

配点 : 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. ( 1 点) S 是 它仅由 a 和 b 变为|S| \leq 10 的字符串

  2. ( 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 的约束。