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≤109
接下来 N 行,每行一个字符串。
所有字符串长度之和不超过1000000。

输出格式

输出一个整数表示答案。

输入样例 复制

样例1:
4 3
set
stop
setting
state

样例2:
5 6
a
rating
rating
b
c

输出样例 复制

样例1:
3

样例2:
6

数据范围与提示

来源:2022 CTU Open