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.
deepl翻译
给你一个由小写拉丁字母和/或问号组成的字符串 。
串联重复是一个偶数长度的字符串，其前半部分等于后半部分。
如果 可以通过删除开头的几个（可能是零个或全部）字符和结尾的几个（可能是零个或全部）字符从 得到，那么字符串 就是字符串 的子串。
您的目标是用某个小写拉丁字母替换每个问号，使串联重复的最长子串的长度尽可能最大。
Input
The 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$.
Output
For 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$.
4
zaabaabz
?????
code?????s
codeforces
6
4
10
0
相关
在下列比赛中: