#P5657. [BJWC2018] 词韵
[BJWC2018] 词韵
题目描述
Adrian 很喜欢诗歌中的韵。记 为单词 与 的最长公共后缀长度。当且仅当
时,两个单词押韵。
给定 个互不相同的单词,可以从中选取若干个单词并任意排列,每个单词最多选一次。要求序列中任意两个相邻单词都押韵,求序列的最大长度。
输入格式
第一行是一个整数 。
接下来 行,每行一个由小写英文字母组成的字符串,表示每个单词。所有单词互不相同。
输出格式
输出一行,为一个整数,表示最长单词序列的长度。
样例 #1
5
ask
psk
k
krafna
sk
4
提示
【样例解释】
一种最长单词序列是 ask、psk、sk、k。
【数据规模和约定】
- 对于 的数据,,所有单词长度之和不超过 。
- 对于所有数据,,所有单词长度之和不超过 。