A14904. Prefix Removals
编程题
普及/提高-
知识点
题目描述
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.
- 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$ .
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".
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".