#P18333. Suspicious Submissions

Suspicious Submissions

Suspicious Submissions

学生们相互分享了代码。你拿到了他们的所有提交,希望找出一些可疑的提交对,手工检查是否存在抄袭。

每份提交是一个由大写英文字母组成的字符串。给定整数 kk,称一对提交 {s,t}\{s,t\} 为 kk 可疑,当且仅当可以把 tt 中一个长度不超过 kk 的连续子串,替换成另一个长度不超过 kk 的字符串,从而得到 ss;反方向也同样成立。

被替换的子串和替换进去的字符串都可以为空。子串必须是原字符串中的一个连续片段。

给定 kk,求有多少对提交是 kk 可疑的。每一对提交只计一次。

输入格式

第一行包含测试用例数 ZZ。

每组测试用例的第一行包含两个整数 n,kn,k,分别表示提交数量和参数。

接下来 nn 行,第 ii 行包含字符串 sis_i,表示第 ii 份提交。同一组内的所有提交互不相同。

输出格式

对于每组测试用例,输出一行一个整数,表示 kk 可疑提交对的数量。

数据范围

  • 1≤Z≤900001\le Z\le90000;
  • 1≤n≤1000001\le n\le100000;
  • 1≤k≤10000001\le k\le1000000;
  • 每个 sis_i 只由大写英文字母组成,同组字符串两两不同;
  • 每组内所有字符串的总长度不超过 10000001000000;
  • 所有测试用例的 nn 之和不超过 200000200000;
  • 所有测试用例中字符串的总长度不超过 20000002000000。

样例输入 1

1
4 2
SUFFIXTREE
SUSIXTREE
SUFFIXTREAP
SUFFIXARRAY

样例输出 1

2

样例说明

只有以下两对字符串是 22 可疑的:

  • SUFFIXTREE 与 SUSIXTREE:将中间的 FF 替换为 S;
  • SUFFIXTREE 与 SUFFIXTREAP:将末尾的 E 替换为 AP。