#P8679. [2019年省队联测]地
[2019年省队联测]地
地 ( floor.cpp )
题目背景
幻想乡地铁修建计划2.0
题目描述
幻想乡有 个重要城镇,每个城镇有官方名称 和民间名称。乡长想在幻想乡修一些地铁,使得两两城镇之间都可以通过地铁互相到达,且修的地铁尽量少。在两个城镇之间修的地铁的和谐度 $w=\operatorname{LCP} ( A_{i} , B_{j} )+\operatorname{LCP} ( B_{i} , A_{j} )$。乡长希望你帮助他求出地铁线路和谐度之和最大的方案。你只需要输出最大的和谐度是多少。
表示字符串 的最长公共前缀长度。
输入格式
第一行一个正整数 。
接下来 行,每行一个字符串 ;再接下来 行,每行一个字符串 。
输出格式
一行一个非负整数,表示最大的和谐度
样例输入1
3
aaa
bbc
bb
bbb
ac
bbc
样例输出1
6
数据规模和约定
全部数据满足 $\sum_{i=1}^n(\lvert A_i\rvert+\lvert B_i\rvert)\le10^5$。
本版沿用现行 Hydro 评分:所有测试点共 100 分,按上述全局范围评测。