Problem D
Typo Squatting
After Coding Cup grew to over $100\, 000$ participants, our website codingcup.se faced a new problem. Spammers started to register domain names that were deceptively similar to ours, differing in just a single letter (such as codingcap.se). Unsuspecting participants sometimes visited these domains instead due to a typo.
After losing a huge chunk of users due to these spam domains, it was time to fight back. Working together with the local Internet domain registrars, you got access to the list of all existing domains. Using this data, you want to try to find domains that are under attack by these spammers.
For each of the registered domains, your task is to find the number of other domains that can be obtained by changing a single letter of the domain to another letter.
Input
The first line of input contains an integer $N \ge 1$, the number of domains.
The next $N$ lines contain one (non-empty) domain name each, consisting only of characters a-z and 0-9. No domain appears twice in the input.
We assume all domains have the same ending (.se), so this is not included in the input domain names.
Output
For each of the $N$ domain names, output the number of other domains that only differ by one character. The answers for the domains should be output in the same order as they appear in the input.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
Let $S$ be the sum of the lengths of all domain names in the input.
|
Group |
Points |
Constraints |
|
$1$ |
$5$ |
$S \le 500$ |
|
$2$ |
$16$ |
$S \le 100\, 000$, all domains have length at most 10 |
|
$3$ |
$14$ |
$S \le 300\, 000$ |
|
$4$ |
$15$ |
$S \le 3\, 000\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 a b aa bb |
1 1 0 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 kodsport kodsp0rt k0dsport |
2 1 1 |
