2222: 词韵
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
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。