← 返回题目列表

Codeforces · 1422/E

E. 明莱克斯

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

不久前,Lesha 发现了一个有趣的字符串 $$$s$$$,由小写英文字母组成。 Lesha立即针对这个字符串开发了一种独特的算法并与大家分享。算法如下。

Lesha 在位置 $$$(i, i + 1)$$$ 上选择任意(可能为零)数量的对,以满足以下条件:

- 对于每对 $$$(i, i + 1)$$$ 不等式 $$$0 \le i < |s| - 1$$$ 成立;
- 对于每对 $$$(i, i + 1)$$$,等式 $$$s_i = s_{i + 1}$$$ 成立;
- 没有索引包含在超过一对中。

Lesha 感兴趣的是通过将算法应用于给定字符串的后缀,他可以获得按字典顺序排列的最小字符串。

输入

唯一一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — 仅由小写英文字母组成的初始字符串。

输出

在 $$$|s|$$$ 行中打印答案的长度和答案本身,从最长后缀的答案开始。输出可能很大,因此,当某些答案长于 $$$10$$$ 字符时,请打印答案的前 $$$5$$$ 字符,然后是“...”,然后是最后 $$$2$$$ 字符。

示例

输入 #1

abcdd

输出 #1

3 abc
2 bc
1 c
0 
1 d

输入 #2

abbcdddeaaffdfouurtytwoo

输出 #2

18 abbcd...tw
17 bbcdd...tw
16 bcddd...tw
15 cddde...tw
14 dddea...tw
13 ddeaa...tw
12 deaad...tw
11 eaadf...tw
10 aadfortytw
9 adfortytw
8 dfortytw
9 fdfortytw
8 dfortytw
7 fortytw
6 ortytw
5 rtytw
6 urtytw
5 rtytw
4 tytw
3 ytw
2 tw
1 w
0 
1 o

注意

考虑第一个例子。

- 最长的后缀是整个字符串“abcdd”。选择一对 $$$(4, 5)$$$,Lesha 获得“abc”。
- 下一个最长的后缀是“bcdd”。选择一对$$$(3, 4)$$$,我们得到“bc”。
- 下一个最长的后缀是“cdd”。选择一对$$$(2, 3)$$$,我们得到“c”。
- 下一个最长的后缀是“dd”。选择一对$$$(1, 2)$$$,我们得到“”(空字符串)。
- 最后一个后缀是字符串“d”。无法选择任何对,所以答案是“d”。

在第二个示例中,对于最长的后缀“abbcdddeaaffdfouurtytwoo”,选择三对 $$$(11, 12)$$$、$$$(16, 17)$$$、$$$(23, 24)$$$,我们得到“abbcdddeaadfortytw”