新单词接龙问题
题目描述
给定一个包含 $n$ 个单词的字典,从中选择若干个单词,按字典序进行单词接龙,使得接龙的长度最大。
新单词接龙的规则:
1. 单词变换:单词 $w_i$ 添加一个字母,删除一个字母,或修改一个字母可以得到单词 $w_i+1$;
2. 字典序接龙:$w_1,w_2,\cdots,w_n$,满足字典序。
输入输出格式
输入格式
第一行一个整数 $n$($1 \le n \le 25,000$),表示字典中单词的总数。接下来 $n$ 行,按字典序输入 $n$ 个单词,每行一个字符串,表示单词,单词仅由小写字母组成,长度在 $1$ 至 $16$ 以内。
输出格式
输出一行一个整数,表示能获得的单词接龙的最大长度。
输入输出样例
输入样例 #1
9
cat
dig
dog
fig
fin
fine
fog
log
wine
输出样例 #1
5
说明
### 样例解释
长度为 $5$ 的单词接龙为:$\texttt{dig\underline afigafin\underline afine\underline awine}$。