QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#10315. Mascot Naming

統計

在组织大型活动时,主办方经常需要处理一些超出其专业范围的琐事。例如,EUC 2025 的首席裁判必须为活动的官方吉祥物取一个名字,同时满足以下限制条件:

  • 该名字必须包含特定的单词作为子序列*,例如活动名称和地点。给定 $n$ 个必须包含的单词列表 $s_1, s_2, \dots, s_n$。
  • 该名字不得包含去年的吉祥物名称 $t$ 作为子序列*。

请帮助首席裁判找到一个合法的吉祥物名称,或者确定不存在这样的名字。

  • 如果字符串 $x$ 可以通过删除字符串 $y$ 中的某些字符(在任意位置)并保持剩余字符的顺序不变而得到,则称 $x$ 是 $y$ 的子序列。例如,abcaxbycz 的子序列,但不是 acbxyz 的子序列。

输入格式

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

接下来的 $n$ 行中,第 $i$ 行包含字符串 $s_i$ ($1 \le |s_i| \le 200\,000$,$s_i$ 由小写英文字母组成),表示必须作为子序列出现的单词列表中的第 $i$ 个单词。这些单词的总长度不超过 $200\,000$,即 $|s_1| + |s_2| + \dots + |s_n| \le 200\,000$。

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

输出格式

如果存在合法的吉祥物名称,输出 YES。否则,输出 NO

如果存在合法的名称,在下一行输出一个合法的名称。你输出的字符串长度必须不超过 $1\,000\,000$,且必须由小写英文字母组成。可以证明,如果存在合法的吉祥物名称,则一定存在满足这些额外约束的名称。

如果存在多个解,输出其中任意一个即可。

样例

输入 1

2
porto
euc
prague

输出 1

YES
poretuco

说明 1

必须作为子序列出现的单词是 portoeuc,而不得作为子序列出现的单词是 prague。吉祥物有许多合法的名称,例如 poretucoxxxpppeortoucyyyy

如果选择 poretuco 作为吉祥物的名称,可以观察到 portoeuc 确实是其子序列(分别在 POReTucOporEtUCo 中高亮显示),而 prague 不是,符合要求。

字符串 poretuc 不是合法的吉祥物名称,因为它不包含 porto 作为子序列。同样,字符串 poretucoague 也不是合法的吉祥物名称,因为它包含 prague 作为子序列。

输入 2

6
credit
debit
money
rich
bank
capitalism
trap

输出 2

YES
moncrdebditeychankpitalism

输入 3

2
axiom
choice
io

输出 3

NO

输入 4

4
aaa
aab
abb
bbb
ba

输出 4

YES
aaabbb

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.