← 返回题目列表

Codeforces · 1654/B

B. 前缀删除

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

给你一个字符串$$$s$$$,由英文字母的小写字母组成。您必须对 $$$s$$$ 执行以下算法:

- 令 $$$x$$$ 为 $$$s$$$ 的最长前缀的长度,该前缀作为连续子字符串出现在 $$$s$$$ 中的其他位置(其他位置也可能与前缀相交)。如果 $$$x = 0$$$,则中断。否则,删除 $$$s$$$ 的前 $$$x$$$ 字符,然后重复。

前缀是由给定字符串的几个首字母组成的字符串,没有任何重新排序。空前缀也是有效前缀。例如,字符串“abcd”有 5 个前缀:空字符串、“a”、“ab”、“abc”和“abcd”。

例如,如果我们对 $$$s =$$$ "abcabdc" 执行算法,

- 最初,“ab”是最长的前缀,它也作为 $$$s$$$ 中的子字符串出现在其他地方,因此 $$$1$$$ 操作后 $$$s =$$$ "cabdc"。
- 那么,“c”是最长的前缀,它也作为 $$$s$$$ 中的子字符串出现在其他地方,因此 $$$2$$$ 操作后 $$$s =$$$ "abdc"。
- 现在 $$$x=0$$$ (因为没有“abdc”的非空前缀也作为 $$$s$$$ 中的子字符串出现在其他地方),因此算法终止。

执行算法后查找字符串的最终状态。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

接下来是 $$$t$$$ 行,每一行都包含一个测试用例的描述。每行包含一个字符串$$$s$$$。给定的字符串仅由英文字母表中的小写字母组成,长度在 $$$1$$$ 和 $$$2 \cdot 10^5$$$ 之间(含)。

保证所有测试用例$$$s$$$的长度总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在执行算法后打印包含字符串 $$$s$$$ 的单行。可以证明这样的字符串非空。

示例

输入 #1

6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

输出 #1

abdc
a
b
deforces
cf
xyzzw

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,无法对$$$s$$$执行任何操作。

在第三个测试用例中,

- 最初,$$$s =$$$“bbbbbbbbbb”。
- $$$1$$$ 操作后,$$$s =$$$ "b"。

在第四个测试用例中,

- 最初,$$$s =$$$“codeforces”。
- $$$1$$$ 操作后,$$$s =$$$“odeforces”。
- 在 $$$2$$$ 操作之后,$$$s =$$$“解除强制”。