No.1994 Confusing Name
タグ : / 解いたユーザー数 128
作問者 :
MasKoaTS
/ テスター :
Kanten4205
👑 Problem Statement
On the social networking service run by Koa, $N$ users numbered $1, 2, \dots, N$ are registered, and the name of user
$i$ $(1 \leq i \leq N)$ is $S_{i}$.
Here, $S_{1}, S_{2}, \dots, S_{N}$ are pairwise distinct as strings.
For a pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$, when all of the following conditions hold,
user $i$ and user $j$ are said to be "look-alikes" of each other.
The lengths of $S_{i}$ and $S_{j}$ are equal.
$S_{i}$ and $S_{j}$ differ from each other in exactly one character.
Formal definition (click to expand)
Written formally, these conditions are as follows.
$|S_{i} | = |S_{j} |$ (where $|S|$ denotes the length of string $S$)
There exists exactly $1$ integer $k$ $(1 \leq k \leq |S_{i}| = |S_{j}|)$ such that $S_{i}[k] \neq S_{j}[k]$.
(where $S[k]$ denotes the $k$-th character from the beginning of string $S$)
For each $i$ $(1 \leq i \leq N)$, find the number of users, among the $(N - 1)$ users other than user $i$, who are "look-alikes" of user $i$.
Constraints
$2 \leq N \leq 5 \times 10^{4}$
$N$ is an integer
$S_{i}$ $(1 \leq i \leq N)$ is a string of lowercase English letters with length at least $1$ and at most $10$
$S_{i} \neq S_{j}$ $(1 \leq i < j \leq N)$
Input
The input is given in the following format.
$N$
$S_{1}$
$S_{2}$
$\vdots$
$S_{N}$
Line $1$ contains $N$
Line $(i+1)$ $(1 \leq i \leq N)$ contains $S_{i}$
Output
Output the answers, $1$ per line, for a total of $N$ lines, followed by a newline at the end.
On line $i$ $(1 \leq i \leq N)$, output the number of users, among the $(N - 1)$ users other than user $i$, who are "look-alikes" of user $i$.
Sample
Sample 1
Input
6 maskoats taskoats mascoats maskoast maskoatt maskoat
Output
3 1 1 1 2 0
First, the "look-alikes" of user $1$ are users $2, 3, 5$, which is $3$ users.
For example, the name "maskoats" of user $1$ and the name "mascoats" of user $3$ both have length
$8$, and they differ only in the $4$-th character from the beginning.
Therefore, the two are "look-alikes" of each other.
User $1$ and user $4$ have user names of equal length, but the last $2$ characters differ, so they are not "look-alikes".
Also, user $1$ and user $6$ have user names of different lengths, so they are not "look-alikes".
Finding the answers for the other users in the same way gives the sample output above.
Sample 2
Input
10 z zz zzz zzzz zzzzz zzzzzz zzzzzzz zzzzzzzz zzzzzzzzz zzzzzzzzzz
Output
0 0 0 0 0 0 0 0 0 0
For every $i$ $(1 \leq i \leq 10)$, among the $9$ users other than user $i$, there is not even $1$ user who is a "look-alike" of user $i$.
Sample 3
Input
16 takashi p hamada yamada abe q takeshi yabe kamada r laplace raplace lhaplus replace loveplus s
Output
1 3 2 2 0 3 1 0 2 3 1 2 0 1 0 3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。