题目描述
小阿德里安是押韵的粉丝。他认为,两个单词押韵当且仅当它们最长的共同后缀与两个单词中的较长后缀一样长,或者比较长的单词短
换句话说,A 和 B 押韵当且仅当它保持 LCS(A, B) ≥ max(|A|, |B|)−
有一天,在阅读短篇小说集时,他决定创作尽可能长的单词序列,使每个连续的单词押韵。序列中的每个单词只能出现一次。
阿德里安已经厌倦了这个任务,所以他决定回去读书,并要求你代替他解决这个任务。
输入格式
输入的第一行包含整数 N(1 ≤ N ≤ 500 000)。
以下 N 行中的每一行都包含一个由英文字母的小写字母组成的单词。所有单词都是相互区分的,其总长度最多为3 000
00 0。
输出格式
必须输出最长序列的长度。
输入输出样例
输入#1
复制
4
honi
toni
oni
ovi
输出#1
复制
3
输入#2
复制
5
ask
psk
krafna
sk
k
输出#2
复制
4
输入#3
复制
5
pas
kompas
stas
s
nemarime
输出#3
复制
1
说明/提示
在价值 30% 点的测试用例中,它将保持 N ≤ 18。
澄清第二个测试用例:
唯一可能的序列是ask-psk-sk-k。
澄清第三个测试用例:
没有两个词押韵。