当前位置:首页 > 枚举 > 正文
洛谷P5876化简单词[NOI导刊]
147+

题目大意:n个单词,我们可以用单词的前缀来表示这个单词,只要他不是其他单词的前缀,请问每个单词化简到最短长度分别是什么?

题目描述

最近情报人员得到了一些经过加密的文章,每个单词都很长。破译人员想到先把单词化简一下,方法是把每个单词尽量取短些的前缀,但所取的前缀不能是其他单词的前缀。

这个任务现在就交给你来完成。

解释:“字符串 $\text{S}_1$ 是 $\text{S}_2$ 的前缀”是说把字符串 $\text{S}_2$ 的后面去掉某些,只保留与 $\text{S}_1$ 相同长度时,$\text{S}_2$ 就与 $\text{S}_1$ 完全相同。如:$\texttt{abc}$ 是 $\texttt{abcaade}$ 和 $\texttt{abc}$ 的前缀,但不是 $\texttt{abadc}$ 的前缀。

输入输出格式

输入格式

第一行一个整数 $N$,表示单词的个数。

下面有 $N$ 行,每行一个单词。

输出格式

共 $N$ 行,每行一个单词,对应上面的 $N$ 个单词化简后的单词。

输入输出样例

输入样例 #1

3   
abc 
efg 
ijh

输出样例 #1

a
e
i

输入样例 #2

3
aac
aad
aae

输出样例 #2

aac
aad
aae

说明

对于 $100\%$ 的数据,$1 \le N \le 50$,每个单词长度不超过 $50$,并且都是由小写字母构成。

保证所给单词没有一个单词是另一个单词的前缀。

解题思路

暴力枚举每个单词的前缀,报名查找是否其他单词的前缀,如果都不是则输出。因为长度从小到大枚举,所以第一次找到的就是答案。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P5876化简单词[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter