311193: CF1948D. Tandem Repeats?
Description
You are given a string $s$, consisting of lowercase Latin letters and/or question marks.
A tandem repeat is a string of an even length such that its first half is equal to its second half.
A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
Your goal is to replace each question mark with some lowercase Latin letter in such a way that the length of the longest substring that is a tandem repeat is maximum possible.
InputThe first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.
The only line of each testcase contains a string $s$ ($1 \le |s| \le 5000$), consisting only of lowercase Latin letters and/or question marks.
The total length of the strings over all testcases doesn't exceed $5000$.
OutputFor each testcase, print a single integer — the maximum length of the longest substring that is a tandem repeat after you replace each question mark in the string with some lowercase Latin letter.
If it's impossible to make any tandem repeat substrings in the string, print $0$.
ExampleInput4 zaabaabz ????? code?????s codeforcesOutput
6 4 10 0
Output
你被给定的一个字符串 s，它由小写拉丁字母和/或问号组成。
串联重复（tandem repeat）是一个长度为偶数的字符串，其前半部分等于后半部分。
如果一个字符串 a 是字符串 b 的子串，那么 a 可以通过从 b 的开头和结尾删除几个（可能是零个或全部）字符来得到。
你的目标是用一些小写拉丁字母替换每个问号，以使得最长的串联重复子串的长度尽可能大。
输入输出数据格式：
输入：
第一行包含一个整数 t（1 ≤ t ≤ 1000）——测试用例的数量。
每个测试用例只有一行，包含一个字符串 s（1 ≤ |s| ≤ 5000），由小写拉丁字母和/或问号组成。
所有测试用例的字符串总长度不超过 5000。
输出：
对于每个测试用例，打印一个整数——在将字符串中的每个问号替换为某些小写拉丁字母后，最长的串联重复子串的最大长度。
如果无法使字符串中出现任何串联重复子串，则打印 0。
示例：
输入：
4
zaabaabz
?????
code?????s
codeforces
输出：
6
4
10
0题目大意： 你被给定的一个字符串 s，它由小写拉丁字母和/或问号组成。 串联重复（tandem repeat）是一个长度为偶数的字符串，其前半部分等于后半部分。 如果一个字符串 a 是字符串 b 的子串，那么 a 可以通过从 b 的开头和结尾删除几个（可能是零个或全部）字符来得到。 你的目标是用一些小写拉丁字母替换每个问号，以使得最长的串联重复子串的长度尽可能大。 输入输出数据格式： 输入： 第一行包含一个整数 t（1 ≤ t ≤ 1000）——测试用例的数量。 每个测试用例只有一行，包含一个字符串 s（1 ≤ |s| ≤ 5000），由小写拉丁字母和/或问号组成。 所有测试用例的字符串总长度不超过 5000。 输出： 对于每个测试用例，打印一个整数——在将字符串中的每个问号替换为某些小写拉丁字母后，最长的串联重复子串的最大长度。 如果无法使字符串中出现任何串联重复子串，则打印 0。 示例： 输入： 4 zaabaabz ????? code?????s codeforces 输出： 6 4 10 0