题目描述

给定一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成。请你找到最短字符串 $k$ 的长度，使得可以将若干个（可能只需一个）$k$ 拼接起来，得到一个与 $s$ 长度相同的新字符串 $c$，并且 $c$ 与 $s$ 至多只有一个字符不同。

更正式地说，要求找到最短的 $k$，使得存在正整数 $x$，满足 $c = \underbrace{k + \cdots + k}_{x\text{ 次}}$，且 $s$ 和 $c$ 长度相同，并且 $c_i \neq s_i$ 的位置最多只有一个（即最多有 $0$ 或 $1$ 个这样的下标 $i$）。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个仅由小写拉丁字母组成的字符串 $s$。

所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例，输出满足题意的最短字符串 $k$ 的长度。

样例

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

1
4
13
2
10

样例说明

在第一个测试用例中，可以选择 $k = \texttt{a}$，此时 $k+k+k+k = \texttt{aaaa}$，与 $s$ 只在第二个位置不同。

在第二个测试用例中，不能选择长度为 $1$ 或 $2$ 的 $k$。可以选择 $k = \texttt{abba}$，此时 $k$ 等于 $s$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1950E，英文题名 Nearly Shortest Repeating Substring。