問題一覧 > 通常問題

No.1994 Confusing Name

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : MasKoaTS / テスター : Kanten4205 👑 potato167
2 ProblemId : 7564 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-28 20:16:47

問題文

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

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

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

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

厳密には（クリックで展開）

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

  • ∣Si∣=∣Sj∣|S_{i} | = |S_{j} | （∣S∣|S| は文字列 SS の長さを表す）

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

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

制約

  • 2≤N≤5×1042 \leq N \leq 5 \times 10^{4}

  • NN は整数

  • SiS_{i} (1≤i≤N)(1 \leq i \leq N) は英小文字からなる長さ 11 以上 1010 以下の文字列

  • Si≠SjS_{i} \neq S_{j} (1≤i<j≤N)(1 \leq i < j \leq N)

入力

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

NN
S1S_{1}
S2S_{2}
 ⋮\vdots
SNS_{N}

  • 11 行目には NN が与えられる

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

出力

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

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

サンプル

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

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

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

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

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

他のユーザに関しても同様に答えを求めると、上の出力例のようになります。

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

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。