No.1994 Confusing Name
タグ : / 解いたユーザー数 139
作問者 :
MasKoaTS
/ テスター :
Kanten4205
👑 
potato167
問題文
コアさんが運営する 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もしくは右上の雲マークをクリックしてアカウントを作成してください。