题解：UVA11488 Hyper Prefix Sets

· · 题解

题意概述

有 n 个字符串，求公共子串长度与所选字串个数积的最大值。

前置知识

字典树，请移步 P8306。

Solution

看到前缀公共长度可以想到用字典树。
然后考虑怎样取才能使得字符串的公共长度和所选字符串成乘积最大。
想到从字典树上每个点的贡献值：

res_i=cnt_i\times dep_i $cnt_i$ 表示以根到 $i$ 为前缀的字符串的个数。 显然我只需要从根节点从上往下遍历字典树，把每个点的贡献值算出来，维护贡献的最大值即可。