【词链】

题目描述

给定一个仅包含小写字母的英文单词表,其中每个单词最多包含 50 个字母。
如果一张由一个词或多个词组成的表中,每个单词(除了最后一个)都是排在它后面的单词的前缀,则称此表为一个词链。例如下面的单词组成了一个词链:
i
int
integer

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

请在给定的单词表中取出一些词,组成最长的词链。最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中,单词互不相同,并且单词按字典顺序排列。

输入格式

第一行一个整数 n ,表示单词表中单词数。
接下来 n 行,每行一个单词。

输出格式

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

样例数据 1

输入

5
i
int
integer
intern
internet

输出

4

备注

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

基本一个裸Trie可以解决,在建的过程中每到终点就打一次标记,下次建的时候统计标记就行了,不过这道题QJC还提供了一种机智的暴力,就是逆着暴力然后遇到第一个能更新的一定是最优解,直接break,效率基本和Trie一样。

Trie代码:

机智暴力代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*