E - Typo Pairs Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

英小文字のみからなる長さ M の文字列が N 個あります。 i 個目 (1\leq i\leq N) の文字列は S_i です。

以下をみたす整数の組 (i,j) (1\leq i < j \leq N) の個数を求めてください。

  • S_i と S_j のハミング距離が 2 以下である。
ハミング距離とは

長さがともに k である文字列 A,B のハミング距離とは、1\leq i\leq k をみたす整数のうち、A の i 文字目と B の i 文字目が異なるようなものの個数を表します。 たとえば、abc と bac のハミング距離は 2 であり、atcoder と contest のハミング距離は 7 です。

制約

  • 2 \leq N \leq 2\times 10^5
  • 2 \leq M \leq 6
  • N,M は整数
  • S_i は英小文字のみからなる長さ M の文字列

入力

入力は以下の形式で標準入力から与えられる。

N M
S_1
S_2
\vdots
S_N

出力

条件をみたす整数の組 (i,j) (1\leq i < j \leq N) の個数を出力せよ。

入力例 1

3 3
abc
abd
bac

出力例 1

2
  • S_1=abc と S_2=abd のハミング距離は 1 です。
  • S_1=abc と S_3=bac のハミング距離は 2 です。
  • S_2=abd と S_3=bac のハミング距離は 3 です。

よって、条件をみたす組は (i,j)=(1,2), (1,3) の 2 つであるため、2 を出力します。

入力例 2

9 5
aaaaa
aaaaa
aaaab
aaaba
aaabb
aabaa
aabab
aabba
aabbb

出力例 2

31

同じ文字列が複数回登場することもあります。

Score : 450 points

Problem Statement

There are N strings of length M consisting of lowercase English letters. The i-th string (1\leq i\leq N) is S_i.

Find the number of integer pairs (i,j) (1\leq i < j \leq N) satisfying the following condition.

  • The Hamming distance between S_i and S_j 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\leq i\leq 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.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 2 \leq M \leq 6
  • N and M are integers.
  • S_i is a string of length M consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the number of integer pairs (i,j) (1\leq i < j \leq N) satisfying the condition.

Sample Input 1

3 3
abc
abd
bac

Sample Output 1

2
  • The Hamming distance between S_1=abc and S_2=abd is 1.
  • The Hamming distance between S_1=abc and S_3=bac is 2.
  • The Hamming distance between S_2=abd and S_3=bac is 3.

Thus, the pairs satisfying the condition are the 2 pairs (i,j)=(1,2), (1,3), so print 2.

Sample Input 2

9 5
aaaaa
aaaaa
aaaab
aaaba
aaabb
aabaa
aabab
aabba
aabbb

Sample Output 2

31

The same string may appear multiple times.