← 返回题目列表

Codeforces · 2068/F

F. 吉祥物命名

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

组织大型活动时,组织者经常会处理其专业范围之外的副业。例如,EUC 2025 的首席裁判必须为赛事的官方吉祥物找到一个名称,同时满足某些限制:

  • 名称必须包含特定单词作为子序列$$$^{\texttt{*}}$$$,例如事件名称和位置。您将获得 $$$n$$$ 所需单词的列表 $$$s_1,\, s_2,\, \ldots,\, s_n$$$。
  • 该名称不得包含去年吉祥物的名称 $$$t$$$ 作为子序列$$$^{\texttt{*}}$$$。
请帮助主审找到一个有效的吉祥物名称或确定不存在。

$$$^{\texttt{*}}$$$ 字符串 $$$x$$$ 是 子序列 字符串 $$$y$$$ 的 ,如果 $$$x$$$ 可以通过删除一些字符(在任何位置)同时保持剩余字符相同的顺序从 $$$y$$$ 获得。例如,$$$\texttt{abc}$$$ 是 $$$\texttt{axbycz}$$$ 的子序列,但不是 $$$\texttt{acbxyz}$$$ 的子序列。

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 200\,000$$$) — 应作为子序列出现的单词数。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含字符串 $$$s_i$$$ ($$$1\le |s_i| \le 200\,000$$$, $$$s_i$$$ 由小写英文字母组成) — 单词列表中应作为子序列出现的第 $$$i$$$ 单词。这些$$$n$$$个单词的总长度最多为$$$200\,000$$$,即$$$|s_1| + |s_2| + \cdots + |s_n| \le 200\,000$$$。

最后一行包含字符串$$$t$$$($$$1\le |t| \le 200\,000$$$,$$$t$$$由小写英文字母组成)——去年吉祥物的名字。

输出

如果吉祥物有有效的名称,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。

如果有有效名称,则在下一行打印有效名称。您打印的字符串长度不得超过 $$$1\,000\,000$$$ 并且必须由小写英文字母组成。人们可以证明,如果吉祥物的有效名称存在,那么就有一个满足这些附加约束。

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

2
porto
euc
prague

输出
复制

YES
poretuco

输入
复制

6
credit
debit
money
rich
bank
capitalism
trap

输出
复制

YES
moncrdebditeychankpitalism

输入
复制

2
axiom
choice
io

输出
复制

NO

输入
复制

4
aaa
aab
abb
bbb
ba

输出
复制

YES
aaabbb

注意

在 第一个样本,必须作为子序列出现的单词是 $$$\texttt{porto}$$$ 和 $$$\texttt{euc}$$$,而不能作为子序列出现的单词是 $$$\texttt{prague}$$$。吉祥物有许多有效名称,例如 $$$\texttt{poretuco}$$$ 或 $$$\texttt{xxxpppeortoucyyyy}$$$。

如果选择 $$$\texttt{poretuco}$$$ 作为吉祥物的名称,请观察 $$$\texttt{porto}$$$ 和 $$$\texttt{euc}$$$ 是子序列(在 $$$\texttt{POReTucO}$$$ 和 $$$\texttt{porEtUCo}$$$ 中突出显示,分别),而 $$$\texttt{prague}$$$ 则不是所期望的。

字符串 $$$\texttt{poretuc}$$$ 不是有效的吉祥物名称,因为它不包含单词 $$$\texttt{porto}$$$ 作为子序列。此外,字符串 $$$\texttt{poretucoague}$$$ 不是有效的吉祥物名称,因为它包含 $$$\texttt{prague}$$$ 作为子序列。