← 返回题目列表

Codeforces · 1950/E

E. 几乎最短的重复子串

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字符组成。找到最短字符串 $$$k$$$ 的长度,使得 $$$k$$$ 的多个(可能是一个)副本可以连接在一起,形成一个与 $$$s$$$ 长度相同且最多一个不同字符的字符串。

更正式地,找到最短字符串 $$$k$$$ 的长度,使得 $$$c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$$$ 对于某个正整数 $$$x$$$,字符串 $$$s$$$ 和 $$$c$$$ 具有相同的长度,并且 $$$c_i \neq s_i$$$ 对于 at大多数$$$i$$$(即存在$$$0$$$或$$$1$$$这样的位置)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 字符串 $$$s$$$ 的长度。

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

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

输出

对于每个测试用例,打印满足语句中约束的最短字符串 $$$k$$$ 的长度。

示例

输入 #1

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

输出 #1

1
4
13
2
10

注意

在第一个测试用例中,您可以选择 $$$k = \texttt{a}$$$ 和 $$$k+k+k+k = \texttt{aaaa}$$$,仅与第二个位置的 $$$s$$$ 不同。

在第二个测试用例中,您不能选择长度为 1 或 2 的 $$$k$$$。我们可以有$$$k = \texttt{abba}$$$,它等于$$$s$$$。