宇宙射线

ID: 10420

远端评测题

2000ms

512MiB

难度: 8

上传者:

标签>

O2优化

Description

有一个长度为 $n$ 的二进制串 $s$ ，你需要找到一个最长的长度为偶数的子串，使得它的前半部分和后半部分完全相同。

但是因为宇宙射线攻击了这个串，有一些位置的值变得未知了。

你可以把未知的值视为 $0$ 和 $1$ 的任意一个数，求出在这种情况下这个最长子串的长度。

本题有多组测试。

第一行一个正整数 $t$ ，表示测试组数。

接下来 $2t$ 行，每两行表示一组测试数据，每组测试数据第一行一个正整数 $n$ ，表示字符串的长度，接下来一行一个长度为 $n$ 的字符串 $s$ 。

$t$ 行，每行一个非负整数，表示第 $i$ 组测试的答案，由于这个串长一定是偶数，所以你只用输出它的长度除以 $2$ 的结果。

4
3

本题采用捆绑测试。

$\text{Subtask}$	分数	$n,t$	特殊性质
$1$	$10$	$n\le 10,t=500$	无特殊限制
$2$		$n\le1000,t=1$	无特殊限制
$3$		$n\le 1000,t=1000$	$A$
$4$		$n\le 1000,t=1000$	无特殊限制
$5$		$n\le 10^4,t=10$
$6$		$n\le 10^4,t=50$
$7$	$20$	$n\le 5\times 10^4,t=2$
$8$	$15$	$n\le 10^5,t=1$
$9$	$5$	$n\le 10^5,t=5$

$A$ ：保证 $s$ 中不存在字符 ?。

保证字符串只由 0,1,? 三种字符组成， $1\le n\le 10^5$ 。