问题 28485 --词韵

28485: 词韵

时间限制: 2 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][10690kb]

题目描述

Adrian 很喜欢诗歌中的韵。他认为,两个单词押韵当且仅当它们的最长公共 后缀的长度至少是其中较长单词的长度减一。也就是说,单词 A 与单词 B 押韵 当且仅当 LCS(A, B) ≥ max(|A|, |B|) – 1。(其中 LCS 是最长公共后缀 longest common suffix 的缩写) 

现在,Adrian 得到了 N 个单词。他想从中选出尽可能多的单词,要求它们能 组成一个单词序列,使得单词序列中任何两个相邻单词是押韵的。

输入

第一行是一个整数 N。 

接下来 N 行,每行一个由小写英文字母组成的字符串,表示每个单词。所有 单词互不相同。

输出

输出一行,为一个整数,表示最长单词序列的长度。

样例输入

5
ask
psk
k
krafna
sk

样例输出

4

提示


【样例解释】 



一种最长单词序列是 ask-psk-sk-k。 



【数据规模和约定】 



30%的测试数据:1 ≤ N ≤ 20,所有单词长度之和不超过 3 000。 



100%的测试数据:1 ≤ N ≤ 500 000,所有单词长度之和不超过 3 000 000。

来源

[提交][状态]