P16170 [ICPC 2015 NAIPC] String Stretching

从一个字符串 $p$ 开始。然后，按如下方式创建一个新字符串 $s$：从空字符串开始，插入 $p$。然后，在字符串中的某个位置（可能包括开头或结尾）再次插入 $p$。然后再一次，再一次。 例如，假设 $p$ 是 **"hello"**。从空字符串开始，可以按如下方式生成一个字符串 $s$（每次新插入的 $p$ 用 **粗体** 表示）： 1. 2. **hello** 3. h**hello**ello 4. hhelloel**hello**lo 5. hhe**hello**lloelhellolo 因此，经过 5 步后，字符串 $s$ 为 **hhehellolloelhellolo**。 给定最终的字符串 $s$，找出可能生成 $s$ 的最短字符串 $p$。如果存在多个长度相同的最短字符串，则找出字典序最小的那个。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入由一行组成，包含一个字符串 $s$。该字符串仅包含小写字母，长度至少为 $1$，至多为 $200$。

输出一行，包含字符串 $p$，即可能生成 $s$ 的最短字符串。

翻译由 DeepSeek V3.2 完成