问题 5472 --单词缩写-【2014暑期训练】T4Day2T1

5472: 单词缩写-【2014暑期训练】T4Day2T1

时间限制: 1 Sec  内存限制: 256 MB
提交: 12  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

单词缩写

【问题描述】

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

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

解释:“字符串s1是s2的前缀”是说把字符串s2的后面去掉某些,只保留与s1相同长度是,s2就与s1完全相同。如:“abc”是“abcaade”和“abc”的前缀,但不是“abadc”的前缀。

数据范围

单词数N,1<=n<=50; 每个单词长度不超过50;并且都是由小写字母构成。

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

【文件输入】

输入文件addreviate.in。

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

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

【文件输出】

输出文件addreviate.out。

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

【输入样例1】

3

abc

efg

ijh

【输出样例1】

a

e

i

【输入样例2】

3

aac

aad

aae

【输出样例2】

aac

aad

aae

提示


    本题数据规模比较小,所以可以用直接模拟的方法去解决。



    对于每一个单词s,从l到length(s)枚举截取前缀的长度,然后判断所截取的前缀是不是其他单词的前缀,若这个前缀不是其他任一单词的前缀,那么这个前缀就是s化简后的单词。



    时间复杂度0(N*N*L)≤50*50*50≈10^6,在1秒内出解。



空间复杂度0(N* L)≤50*50.很小。

来源

 

[提交][状态]