Это усложненная версия этой задачи. Различия в ограничениях на сумму длин строк и на количество тестовых случаев. Вы можете делать взломы, только если обе версии этой задачи решены.
Вам дана строка \(s\), состоящая из строчных букв латинского алфавита. Вы должны найти строку \(t\) максимальной длины, которая удовлетворяет следующим условиям:
- Длина строки \(t\) не превосходит длину строки \(s\).
- \(t\) является палиндромом, то есть она равна себе перевернутой.
- Существует две строки \(a\) и \(b\) (возможно пустые), такие что \(t = a + b\) (здесь операция «\(+\)» это конкатенация строк) и \(a\) является префиксом строки \(s\) и \(b\) является суффиксом строки \(s\).
Выходные данные
Для каждого тестового случая выведите строку максимальной длины, которая удовлетворяет описанным условиям. Если существует несколько решений, вы можете вывести любое.
Примечание
В первом тестовом случае, вся строка \(s = \)«a» удовлетворяет всем условиям.
Во втором тестовом случае, строка «abcdfdcba» удовлетворяет всем условиям, потому что:
- ее длина равна \(9\), что не превосходит длину строки \(s\), которая равна \(11\);
- она палиндром;
- «abcdfdcba» \(=\) «abcdfdc» \(+\) «ba», где строка «abcdfdc» является префиксом строки \(s\) и строка «ba» является суффиксом строки \(s\).
Можно доказать, что невозможно найти более длинную такую строку.
В четвертом тестовом случае, строка «c» это правильный ответ, потому что «c» \(=\) «c» \(+\) «» и это допустимо, потому что по условию строки \(a\) и \(b\) могут быть пустыми. Другой возможный ответ на этот тест это строка «s».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
|
a
abcdfdcba
xyzyx
c
abba
|