[Trie树] Rima

题目

题目描述

Adrian对单词押韵很感兴趣。如果两个单词的最长公共后缀的长度与两个单词中较长那个的长度一样，或者等于较长单词的长度减一，则这两个单词押韵。换句话说，如果A,B的最长公共后缀LCS（A，B）≥max（|A|，|B|）-1，则A和B押韵。

有一天，在阅读一套短篇小说时，他决定创造出能够使每两个相邻单词押韵的最长的单词序列，序列中的每个单词只能出现一次。但是Adrian已经厌倦了这个任务，所以他决定回去读小说，并要求你代替他解决这个任务。

输入

第一行输入包含整数N（1≤N≤5*1e5）。表示单词的个数。

接下来N行每行包含一个只由小写英文字母组成的字符串。表示可以用于组成序列的单词。数据保证每个单词都是不同的，保证所有单词的长度之和不超过3*1e6。

输出

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

样例输入

4
honi
toni
oni
ovi

样例输出

3

题解

Trie树不用说了吧，应该一下就能看出来，就是要反向建树

然后就是一波神奇的操作，我们用树形DP搞，定义$dp[i]$为从$i$节点往下连续终结点（就是一个字符串结束的点）的最大值

然后我们就可以用这个$dp$做答案了，定义$ans[i]$为$i$点往下能得到的所有字符串组合所能得到的最大序列，那么$ans[$

今天的文章[Trie树] Rima分享到此就结束了，感谢您的阅读。