← 返回题目列表

Codeforces · 2121/B

B. 云层之上

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

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由拉丁字母的小写字母组成。判断是否存在三个 非空 字符串 $$$a$$$、$$$b$$$ 和 $$$c$$$ 使得:

  • $$$a + b + c = s$$$,表示字符串 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的串联 $$$^{\text{∗}}$$$ 等于 $$$s$$$。
  • 字符串 $$$b$$$ 是字符串 $$$a + c$$$ 的子字符串 $$$^{\text{†}}$$$,它是字符串 $$$a$$$ 和 $$$c$$$ 的串联。

$$$^{\text{*}}$$$字符串 $$$a$$$ 和 $$$b$$$ 的串联定义为字符串 $$$a + b = a_1a_2 \ldots a_pb_1b_2 \ldots b_q$$$,其中 $$$p$$$ 和 $$$q$$$ 是字符串 $$$a$$$ 的长度,分别是$$$b$$$。例如,字符串“的串联”代码“和”力量“是”代码力量".

$$$^{\text{†}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

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

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出“是"如果存在三个满足条件的非空字符串$$$a$$$、$$$b$$$和$$$c$$$,并且"No”否则。

您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是", "是“,和”是”将被识别为肯定答案。

示例

输入
复制

12
3
aaa
3
aba
3
aab
4
abca
4
abba
4
aabb
5
abaca
5
abcda
5
abcba
6
abcbbf
6
abcdaa
3
abb

输出
复制

Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes

注意

在第一个测试用例中,存在唯一的非空字符串 $$$a$$$、$$$b$$$ 和 $$$c$$$,使得 $$$a + b + c = s$$$。这些是字符串 $$$a =$$$ "a“,$$$b =$$$”a”,并且 $$$c =$$$ ”a"。字符串 $$$a$$$ 和 $$$c$$$ 的串联等于 $$$a + c = $$$ "aa"。字符串 $$$b$$$ 是该字符串的子字符串。

在第六个测试用例中,可以选择 $$$a = $$$ "a“,$$$b = $$$”ab“,并且$$$c = $$$”b"。字符串 $$$a$$$ 和 $$$c$$$ 的串联等于 $$$a + c = $$$ "ab"。字符串 $$$b$$$ 是该字符串的子字符串。

在第七个测试用例中,可以选择 $$$a = $$$ "ab“,$$$b = $$$”a“,并且$$$c = $$$”ca"。字符串 $$$a$$$ 和 $$$c$$$ 的串联等于 $$$a + c = $$$ "abca"。字符串 $$$b$$$ 是该字符串的子字符串。