网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
词链
成绩 | 0 | 开启时间 | 2013年01月18日 星期五 13:05 |
折扣 | 0.8 | 折扣时间 | 2013年01月18日 星期五 13:05 |
允许迟交 | 是 | 关闭时间 | 2013年01月18日 星期五 13:05 |
输入文件 | link.in | 输出文件 | link.out |
【问题描述】
给定一个仅包含小写字母的英文单词表,其中每个单词最多包含 50 个字母。
如果一张由一个词或多个词组成的表中,每个单词(除了最后一个)都是排在它后面的单词的前缀,则称此表为一个词链。例如下面的单词组成了一个词链:
i
int
integer
而下面的单词不组成词链:
integer
intern
请在给定的单词表中取出一些词,组成最长的词链。最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中,单词互不相同,并且单词按字典顺序排列。
【输入格式】
第一行一个整数 n ,表示单词表中单词数。
下接 n 行每行一个单词。
【输出格式】
一个整数,表示最长词链长度。
【输入输出样例】
输入:
link.in
5
i
int
integer
intern
internet
输出:
link.out
4
【数据范围】
50% 的数据, n<=1000
100% 的数据, n<=10000