CF1654B Prefix Removals

给定一个只包含小写英文字母的字符串 $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" 没有非空前缀在其它地方作为子串出现），算法终止。 请输出执行完算法后字符串的最终状态。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来有 $t$ 行，每行一个字符串 $s$。每个字符串只包含小写英文字母，长度在 $1$ 到 $2 \cdot 10^5$ 之间。 保证所有测试用例中字符串的总长度不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行，表示执行完算法后的字符串。可以保证该字符串非空。

第一个测试用例的过程在题目描述中已给出。 第二个测试用例中，无法对 $s$ 进行任何操作。 第三个测试用例： - 初始时，$s = $ "bbbbbbbbbb"。 - 第 1 次操作后，$s = $ "b"。 第四个测试用例： - 初始时，$s = $ "codeforces"。 - 第 1 次操作后，$s = $ "odeforces"。 - 第 2 次操作后，$s = $ "deforces"。 由 ChatGPT 4.1 翻译