RYIP在线题库
首 页   >   习题练习   >   提交
Problem2306--词链

2306: 词链

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

给定一个仅包含小写字母的英文单词表,其中每个单词最多包含50个字母。

如果一张由一个词或多个词组成的表中,每个单词(除了最后一个)都是排在它后面的单词的前缀,则称此表为一个词链。例如下面的单词组成了一个词链:

i
int
integer

而下面的单词不组成词链:

integer
intern

请在给定的单词表中取出一些词,组成最长的词链。最长的词链就是包含单词数最多的词链。

数据保证给定的单词表中,单词互不相同,并且单词按字典顺序排列。


【 Input 】

第一行一个整数n,表示单词表中单词数

下接n行每行一个单词。

【 Output 】

一个整数,表示最长词链长度。

【 Sample Input 】

5
i
int
integer
intern
internet

【 Sample Output 】

4

【HINT】

【数据范围】
50%的数据,n<=1000
100%的数据,n<=10000

【 Source/Category 】