← 返回题目列表

Codeforces · 1326/D1

D1. 前缀-后缀回文(简单版)

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

这是问题的简单版本。不同之处在于对字符串长度总和和测试用例数量的约束。只有解决了该任务的所有版本,您才能进行黑客攻击。

给你一个字符串$$$s$$$,由小写英文字母组成。找到最长的字符串$$$t$$$,它满足以下条件:

- $$$t$$$ 的长度不超过 $$$s$$$ 的长度。
- $$$t$$$ 是回文。
- 存在两个字符串$$$a$$$和$$$b$$$(可能为空),使得$$$t = a + b$$$(“$$$+$$$”表示连接),并且$$$a$$$是$$$s$$$的前缀,而$$$b$$$是$$$s$$$的后缀。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$),即测试用例的数量。接下来的 $$$t$$$ 行每行描述一个测试用例。

每个测试用例都是一个非空字符串$$$s$$$,由小写英文字母组成。

保证所有测试用例的字符串长度总和不超过$$$5000$$$。

输出

对于每个测试用例,打印满足上述条件的最长字符串。如果存在多种可能的解决方案,请打印其中任何一个。

示例

输入 #1

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

输出 #1

a
abcdfdcba
xyzyx
c
abba

注意

在第一个测试中,字符串 $$$s = $$$"a" 满足所有条件。

在第二个测试中,字符串“abcdfdcba”满足所有条件,因为:

- 其长度为$$$9$$$,不超过字符串$$$s$$$的长度,等于$$$11$$$。
- 这是一个回文。
- "abcdfdcba" $$$=$$$ "abcdfdc" $$$+$$$ "ba",并且 "abcdfdc" 是 $$$s$$$ 的前缀,而 "ba" 是 $$$s$$$ 的后缀。

可以证明不存在更长的满足条件的字符串。

在第四个测试中,字符串“c”是正确的,因为“c”$$$=$$$“c”$$$+$$$“”和$$$a$$$或$$$b$$$可以为空。该测试的另一个可能的解决方案是“s”。