L-字符串匹配太多了！_2025年华为杯广东工业大学程序设计竞赛（同步赛）

字符串匹配太多了！

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

塑料正在学 KMP 字符串匹配，以下是他写的获取匹配函数数组的代码：

如果你看不懂代码中 $A$ 到底指什么，这里有一份塑料留下的使用说明书：

定义 $P(S,T)$ 为同时是字符串 $S$ 的后缀和字符串 $T$ 的前缀的最长字符串，则 $\operatorname{Match}(S,T)$ 函数返回的数组 $A$ 中 $A_i$ 等于 $P(S[1...i],T)$ 的长度，其中 $S[1...i]$ 为 $S$ 的长度为 $i$ 的前缀 $\dagger$ 。特别的，若不存在这样的字符串，则 $A_i = 0$ 。

塑料测试了一下，当 $S=\texttt{caabab}$ 而 $T=\texttt{aba}$ 时，得到 $\textstyle \operatorname{Match}(S,T)=[0,1,1,2,3,2]$ 。

现在给你两个长度均为 $n$ 的字符串 $S_1, S_2$ ，其中这两个字符串都只由 abc 三种字符构成，而塑料想知道是否存在一个字符串 $T$ 使得 $\textstyle \operatorname{Match}(S_1,T) = \operatorname{Match}(S_2,T)$ 。

当你认为有解时，为了证实确实存在这样的字符串，还请构造一个合法的 $T$ 出来，要求字符串长度在 $1$ 到 $n$ 之间，且 $T$ 也只由 abc 三种字符构成。

$\dagger$ 对于一个字符串 $s$ ，长度为 $x$ 的前缀为 $s_{1}s_{2}\dots s_{x}$ 如字符串 abcde 的长度为 $3$ 的前缀为 abc。

输入描述:

本题有多组测试样例。

第一行输入一个正整数 $T$ ( $1 \leq T \leq 2 \times 10^5$ )，表示有 $T$ 组样例。

接下来对于每组测试样例，输入三行：

第一行输入一个正整数 $n$ ( $1 \leq n \leq 10^6$ ) 表示字符串 $S_1,S_2$ 的长度；

第二行和第三行分别输入 $S_1,S_2$ 。

保证单个测试点内所有测试样例的 $n$ 之和不超过 $10^6$ 。

输出描述:

对于每组测试样例，

若有解，请你先输出一个YES，然后输出一行一个正整数 $m$ ，表示你构造的字符串 $T$ 的长度，然后再输出字符串 $T$ ；

若无解，只需要输出NO即可。

你可以以任意大小写输出Yes和No（例如，字符串yEs、yes、Yes和YES将被识别为肯定的回答）。

示例1

输入

复制

2
4
aaaa
aaab
6
abcabc
aaaaaa

输出

复制

YES
4
caac
NO