这是问题的困难版本。不同之处在于对字符串长度总和和测试用例数量的约束。只有解决了该任务的所有版本,您才能进行黑客攻击。
给你一个字符串$$$s$$$,由小写英文字母组成。找到最长的字符串$$$t$$$,它满足以下条件:
- $$$t$$$ 的长度不超过 $$$s$$$ 的长度。
- $$$t$$$ 是回文。
- 存在两个字符串$$$a$$$和$$$b$$$(可能为空),使得$$$t = a + b$$$(“$$$+$$$”表示串联),并且$$$a$$$是$$$s$$$的前缀,而$$$b$$$是$$$s$$$的后缀。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$),测试用例的数量。接下来的 $$$t$$$ 行每行描述一个测试用例。
每个测试用例都是一个非空字符串$$$s$$$,由小写英文字母组成。
保证所有测试用例的字符串长度总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印满足上述条件的最长字符串。如果存在多种可能的解决方案,请打印其中任何一个。
示例
输入 #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”。