P5799.md

[SEERC2019]Cycle String?

题目描述

大法师给了 Alice 和 Bob 一个长度为 $2 \cdot n$ 的环形字符串，这个环形字符串中没有重复的长为 $n$ 的子串。在一个环形字符串中，字符 $s_{i+1}$ 在 $s_i$之后，而 $s_1$ 在 $s_{2n}$ 之后。

不幸的是，恶魔打乱了字符串中字符的顺序。帮助 Alice 和 Bob 将字符串还原成满足上述要求的原始字符串。

输入格式

第一行包含一个长度为 $2 \cdot n \ (2 \leq 2\cdot n \leq 1 \ 000 \ 000)$ 的字符串 $s$，字符串中只包含小写字母。

输出格式

如果能够将字符串还原成满足要求的字符串，则在第一行输出 NO；如果无法还原，则在第一行输出 YES。

如果有解，在第二行输出还原后的字符串。如果存在多解，输出任意一个即可。

样例 #1

样例输入 #1

cbbabcacbb

样例输出 #1

YES
abbabcbccb

样例 #2

样例输入 #2

aa

样例输出 #2

NO

样例 #3

样例输入 #3

afedbc

样例输出 #3

YES
afedbc

提示

第一个样例中，还原后的字符串中的子串分别为：abbab、bbabc、babcb、abcbc、bcbcc、cbccb、bccba、ccbab、babba。

注意到第一个样例的答案中并不含有重复的子串，但存在其他的答案也满足题目要求。因此答案不唯一，样例只提供了一种满足要求的输出。

第二个样例中，无法将字符串还原为满足要求的原始字符串。

第三个样例中，不需要做任何操作即满足要求。