2140: 前缀压缩技术

内存限制:1024 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:111 通过:69

题目描述

现有一个网站有 n 个用户,每个用户名均为长度为 L 个字符串,存储所有用户名需要存储 n*L 个字符。
现在有一个压缩内存的方法:不必存储每个用户完整用户名,只需存储该用户名的前缀,只要没有其他用户名具有相同的前缀即可。
例如,如果只有 james 和 jacob 这两个名称,仅存储 jam 和 jac,并仍能够识别它们两个。
利用该压缩技术,存储 n 个用户名需要多少个字符?

输入格式

第一行为正整数 n,L,2≤n≤10000,1≤L≤1000。输入保证 n * L ≤ 1000000。
接下来 n 行,每行一个长度为 L 的字符串,仅包含小写字母,且所有字符串互不相同。

输出格式

输出一个整数表示答案。

输入样例 复制

样例1:
2 5
james
jacob

样例2:
4 4
xxxx
yxxx
xxyx
yxxy

输出样例 复制

样例1:
6

样例2:
14

数据范围与提示

来源:2022.BAPC