Prefix Removals

题意翻译

给定一个字符串 $s$。现在对其执行如下操作： - 令 $x$ 为最长的使得其等同于一个非前缀的子串的前缀长度（例如对于 $s=\texttt{abcabdc}$，$x=2$）。如果 $x=0$，停止操作；否则，去掉长度为 $x$ 的前缀，并重复操作。 求出在执行上述操作后得到的字符串。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant \left|s\right|,\sum \left|s\right|\leqslant 2\times 10^5$。 Translated by Eason_AC

题目描述

You are given a string $ s $ consisting of lowercase letters of the English alphabet. You must perform the following algorithm on $ s $ : - Let $ x $ be the length of the longest prefix of $ s $ which occurs somewhere else in $ s $ as a contiguous substring (the other occurrence may also intersect the prefix). If $ x = 0 $ , break. Otherwise, remove the first $ x $ characters of $ s $ , and repeat. A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd". For instance, if we perform the algorithm on $ s = $ "abcabdc", - Initially, "ab" is the longest prefix that also appears somewhere else as a substring in $ s $ , so $ s = $ "cabdc" after $ 1 $ operation. - Then, "c" is the longest prefix that also appears somewhere else as a substring in $ s $ , so $ s = $ "abdc" after $ 2 $ operations. - Now $ x=0 $ (because there are no non-empty prefixes of "abdc" that also appear somewhere else as a substring in $ s $ ), so the algorithm terminates. Find the final state of the string after performing the algorithm.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. This is followed by $ t $ lines, each containing a description of one test case. Each line contains a string $ s $ . The given strings consist only of lowercase letters of the English alphabet and have lengths between $ 1 $ and $ 2 \cdot 10^5 $ inclusive. It is guaranteed that the sum of the lengths of $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single line containing the string $ s $ after executing the algorithm. It can be shown that such string is non-empty.

输入输出样例

输入样例 #1

6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

输出样例 #1

abdc
a
b
deforces
cf
xyzzw

说明

The first test case is explained in the statement. In the second test case, no operations can be performed on $ s $ . In the third test case, - Initially, $ s = $ "bbbbbbbbbb". - After $ 1 $ operation, $ s = $ "b". In the fourth test case, - Initially, $ s = $ "codeforces". - After $ 1 $ operation, $ s = $ "odeforces". - After $ 2 $ operations, $ s = $ "deforces".