AT_abc483_e.Typo Pairs
提高+/省选-
通过率:0%
时间限制:4.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N strings of length M consisting of lowercase English letters. The i-th string (1≤i≤N) is Si.
Find the number of integer pairs (i,j) (1≤i<j≤N) satisfying the following condition.
- The Hamming distance between Si and Sj is at most 2.
What is Hamming distance?
The Hamming distance between strings A and B, both of length k, is the number of integers i satisfying 1≤i≤k such that the i-th character of A and the i-th character of B are different. For example, the Hamming distance between abc and bac is 2, and the Hamming distance between atcoder and contest is 7.
有 N 个长度为 M 的字符串,均由小写英文字母组成。第 i 个字符串(1≤i≤N)为 Si。
请找出满足以下条件的整数对 (i,j)(其中 1≤i<j≤N)的个数:
- Si 与 Sj 的汉明距离至多为 2。
什么是汉明距离?
对于两个长度均为 k 的字符串 A 和 B,其汉明距离定义为满足 1≤i≤k 且 A 的第 i 个字符与 B 的第 i 个字符不同的整数 i 的个数。例如,abc 与 bac 的汉明距离为 2,而 atcoder 与 contest 的汉明距离为 7。
输入格式
The input is given from Standard Input in the following format:
N M
S1
S2
⋮
SN
输入从标准输入中按以下格式给出:
N M
S1
S2
⋮
SN
输出格式
Print the number of integer pairs (i,j) (1≤i<j≤N) satisfying the condition.
输出满足条件的整数对 (i,j) (1≤i<j≤N) 的个数。
输入输出样例
输入#1
3 3 abc abd bac
输出#1
2
输入#2
9 5 aaaaa aaaaa aaaab aaaba aaabb aabaa aabab aabba aabbb
输出#2
31
说明/提示
Sample 1 Explanation:
- The Hamming distance between S1=
abcand S2=abdis 1. - The Hamming distance between S1=
abcand S3=bacis 2. - The Hamming distance between S2=
abdand S3=bacis 3.
Thus, the pairs satisfying the condition are the 2 pairs (i,j)=(1,2), (1,3), so print 2.
Sample 2 Explanation:
The same string may appear multiple times.
Constraints
- 2≤N≤2×105
- 2≤M≤6
- N and M are integers.
- Si is a string of length M consisting of lowercase English letters.
样例 1 解释:
- S1=
abc与 S2=abd的汉明距离为 1。 - S1=
abc与 S3=bac的汉明距离为 2。 - S2=
abd与 S3=bac的汉明距离为 3。
因此,满足条件的数对为 (i,j)=(1,2) 和 (1,3),共 2 对,故输出 2。
样例 2 解释:
同一字符串可能出现多次。
约束条件
- 2≤N≤2×105
- 2≤M≤6
- N 与 M 均为整数。
- 每个 Si 是一个长度为 M 的字符串,仅由小写英文字母组成。
输入解题思路,AI测评打分。不知道怎么写?