問題一覧 > 通常問題

No.1994 Confusing Name

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : MasKoaTSMasKoaTS / テスター : Kanten4205Kanten4205 👑 potato167potato167
2 ProblemId : 7564 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-19 19:13:29

問題文

コアさんが運営する SNS では、$1, 2, \dots, N$ の番号が付いた $N$ 人のユーザが登録をしており、
ユーザ $i$ $(1 \leq i \leq N)$ の名前は $S_{i}$ です。
ただし、$S_{1}, S_{2}, \dots, S_{N}$ は文字列として互いに異なります。

$1 \leq i < j \leq N$ を満たす整数の組 $(i,j)$ に対して次の条件がすべて満たされるとき、
ユーザ $i$ とユーザ $j$ は互いに「そっくりさん」の関係にあると言います。

  • $S_{i}$ と $S_{j}$ の長さが互いに等しい。

  • $S_{i}$ と $S_{j}$ が互いに一文字だけ異なる。

> 厳密には(クリックで展開)

これらの条件を厳密に記述すると、次のようになります。

  • $|S_{i} | = |S_{j} |$ ($|S|$ は文字列 $S$ の長さを表す)

  • $S_{i}[k] \neq S_{j}[k]$ となる整数 $k$ $(1 \leq k \leq |S_{i}| = |S_{j}|)$ がただ $1$ つ存在する。
    ($S[k]$ は文字列 $S$ の先頭から $k$ 番目の文字を表す)

各 $i$ $(1 \leq i \leq N)$ ごとに、ユーザ $i$ を除く $(N - 1)$ 人のユーザのうち
ユーザ $i$ と「そっくりさん」の関係にある者の人数を求めてください。

制約

  • $2 \leq N \leq 5 \times 10^{4}$

  • $N$ は整数

  • $S_{i}$ $(1 \leq i \leq N)$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列

  • $S_{i} \neq S_{j}$ $(1 \leq i < j \leq N)$

入力

入力は次の形式で与えられます。

$N$
$S_{1}$
$S_{2}$
 $\vdots$
$S_{N}$
  • $1$ 行目には $N$ が与えられる

  • $(i+1)$ $(1 \leq i \leq N)$ 行目には $S_{i}$ が与えられる

出力

答えを $1$ 行ずつ合計 $N$ 行に出力し、最後に改行してください。

$i$ $(1 \leq i \leq N)$ 行目には、ユーザ $i$ を除く $(N - 1)$ 人のユーザのうち
ユーザ $i$ と「そっくりさん」の関係にある者の人数を出力してください。

サンプル

サンプル1
入力
6
maskoats
taskoats
mascoats
maskoast
maskoatt
maskoat
出力
3
1
1
1
2
0

まず、ユーザ $1$ と「そっくりさん」の関係にあるのはユーザ $2, 3, 5$ の $3$ 人です。

例えば、ユーザ $1$ の名前「maskoats」とユーザ $3$ の名前「mascoats」は
どちらも長さが $8$ であり、先頭から $4$ 番目の文字だけが互いに異なります。
そのため、両者は互いに「そっくりさん」の関係にあります。

ユーザ $1$ とユーザ $4$ は、ユーザ名の長さは互いに等しいですが、
末尾 $2$ 文字が互いに異なるので、「そっくりさん」の関係にはありません。

また、ユーザ $1$ とユーザ $6$ は、ユーザ名の長さが互いに異なるので、
「そっくりさん」の関係にはありません。

他のユーザに関しても、同様に答えを求めてください。

サンプル2
入力
10
z
zz
zzz
zzzz
zzzzz
zzzzzz
zzzzzzz
zzzzzzzz
zzzzzzzzz
zzzzzzzzzz
出力
0
0
0
0
0
0
0
0
0
0

どの $i$ $(1 \leq i \leq 10)$ に対しても、ユーザ $i$ を除く $9$ 人のユーザのうち
ユーザ $i$ と「そっくりさん」の関係にある者は $1$ 人もいません。

サンプル3
入力
16
takashi
p
hamada
yamada
abe
q
takeshi
yabe
kamada
r
laplace
raplace
lhaplus
replace
loveplus
s
出力
1
3
2
2
0
3
1
0
2
3
1
2
0
1
0
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。