#P18333. Suspicious Submissions
Suspicious Submissions
Suspicious Submissions
学生们相互分享了代码。你拿到了他们的所有提交,希望找出一些可疑的提交对,手工检查是否存在抄袭。
每份提交是一个由大写英文字母组成的字符串。给定整数 ,称一对提交 为 可疑,当且仅当可以把 中一个长度不超过 的连续子串,替换成另一个长度不超过 的字符串,从而得到 ;反方向也同样成立。
被替换的子串和替换进去的字符串都可以为空。子串必须是原字符串中的一个连续片段。
给定 ,求有多少对提交是 可疑的。每一对提交只计一次。
输入格式
第一行包含测试用例数 。
每组测试用例的第一行包含两个整数 ,分别表示提交数量和参数。
接下来 行,第 行包含字符串 ,表示第 份提交。同一组内的所有提交互不相同。
输出格式
对于每组测试用例,输出一行一个整数,表示 可疑提交对的数量。
数据范围
- ;
- ;
- ;
- 每个 只由大写英文字母组成,同组字符串两两不同;
- 每组内所有字符串的总长度不超过 ;
- 所有测试用例的 之和不超过 ;
- 所有测试用例中字符串的总长度不超过 。
样例输入 1
1
4 2
SUFFIXTREE
SUSIXTREE
SUFFIXTREAP
SUFFIXARRAY
样例输出 1
2
样例说明
只有以下两对字符串是 可疑的:
SUFFIXTREE与SUSIXTREE:将中间的FF替换为S;SUFFIXTREE与SUFFIXTREAP:将末尾的E替换为AP。