New Online Judge
主页
问题
来源/分类
竞赛&作业
状态
排名
常见问答
登录
注册
2161: 公共前缀之和
内存限制:512 MB
时间限制:2 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:7
通过:2
提交
提交记录
统计
题目描述
定义:函数 f(s,t) 表示字符串 s 和字符串 t 的公共前缀长度。例如 f("stop", "state") = 2。
现在给定 n 个字符串记为 A[1],A[2],...,A[n]。
请求出存在多少个连续区间 [l, r] 满足:
区间中两两字符串的公共前缀长度之和大于等于 k
。
形式化定义:请求出存在多少个二元组<l,r>满足:
1≤l<
r
≤n;
Sum(f(A[i],A[j])) ≥ k,i,j∈[l,r],i < j。
输入格式
第一行为正整数 N 和 K,1≤N
≤1000000,1
≤K
≤10
9
。
接下来 N 行,每行一个字符串。
所有字符串长度之和不超过1000000。
输出格式
输出一个整数表示答案。
输入样例
复制
样例1: 4 3 set stop setting state 样例2: 5 6 a rating rating b c
输出样例
复制
样例1: 3 样例2: 6
数据范围与提示
来源:2022 CTU Open
分类标签
进阶题
字典树