AT_abc480_b.Invalid Vote

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

NN candidates 1,2,…,N1,2,\dots,N are running in an election. The name of each candidate consists of lowercase English letters, and the names are distinct. The name of candidate ii is SiS_i.

MM ballots 1,2,…,M1,2,\dots,M were cast, and ballot jj has a string TjT_j consisting of lowercase English letters written on it.

If there is a candidate whose name exactly matches TjT_j, that candidate receives 11 vote. Otherwise, if there is exactly one candidate whose name can be obtained by changing 11 character of TjT_j, that candidate receives 11 vote. Otherwise, the ballot is invalid.

For each i=1,2,…,Ni=1,2,\dots,N, find how many votes candidate ii receives.

NN 名候选人 1,2,…,N1,2,\dots,N 参加一场选举。每位候选人的姓名由小写英文字母组成,且所有姓名互不相同。候选人 ii 的姓名为 SiS_i。

共投出 MM 张选票,编号为 1,2,…,M1,2,\dots,M,其中第 jj 张选票上写有一个由小写英文字母组成的字符串 TjT_j。

  • 若存在某位候选人的姓名恰好等于 TjT_j,则该候选人获得 11 票;
  • 否则,若恰好存在一位候选人,其姓名可通过将 TjT_j 恰好修改一个字符得到,则该候选人获得 11 票;
  • 其他情况下,该选票作废(不计入任何候选人票数)。

对每个 i=1,2,…,Ni=1,2,\dots,N,求候选人 ii 获得的票数。

输入格式

The input is given from Standard Input in the following format:

NN MM
S1S_1
S2S_2
⋮\vdots
SNS_N
T1T_1
T2T_2
⋮\vdots
TMT_M

输入从标准输入中按以下格式给出:

NN MM
S1S_1
S2S_2
⋮\vdots
SNS_N
T1T_1
T2T_2
⋮\vdots
TMT_M

输出格式

Print NN lines in total.
The ii-th line should contain the number of votes candidate ii receives.

共输出 NN 行。
第 ii 行应包含候选人 ii 所获得的票数。

输入输出样例

  • 输入#1

    5 8
    takahashi
    aoki
    sato
    kato
    kano
    aoki
    takanashi
    sano
    atcoder
    chokudai
    kato
    aoki
    yato

    输出#1

    1
    2
    0
    1
    0
  • 输入#2

    2 5
    a
    b
    a
    b
    c
    a
    aa

    输出#2

    2
    1

说明/提示

Sample 1 Explanation:
There are 55 candidates: takahashi, aoki, sato, kato, and kano.
Ballot 11 has aoki written on it.
Candidate 22 receives 11 vote.

Ballot 22 has takanashi written on it.
Changing the 55-th character from n to h makes it match the name of candidate 11, and there is no other such candidate, so candidate 11 receives 11 vote.

Ballot 33 has sano written on it.
Changing the 33-rd character from n to t makes it match the name of candidate 33, and changing the 11-st character from s to k makes it match the name of candidate 55, so this ballot is invalid.

Constraints

  • 1≤N≤1001 \leq N \leq 100
  • 1≤M≤1001 \leq M \leq 100
  • 1≤∣Si∣≤101 \leq |S_i| \leq 10
  • Si≠SjS_i \neq S_j if i≠ji \neq j.
  • 1≤∣Tj∣≤101 \leq |T_j| \leq 10
  • SiS_i and TjT_j are strings consisting of lowercase English letters.
  • NN and MM are integers.

样例 1 解释:
共有 55 位候选人,其姓名分别为 takahashi、aoki、sato、kato 和 kano。
第 11 张选票上写着 aoki,因此候选人 22 获得 11 票。

第 22 张选票上写着 takanashi。
将第 55 个字符从 n 改为 h 后,该字符串与候选人 11 的姓名匹配,且不存在其他候选人满足此条件,因此候选人 11 获得 11 票。

第 33 张选票上写着 sano。
将第 33 个字符从 n 改为 t 后,该字符串与候选人 33 的姓名匹配;而将第 11 个字符从 s 改为 k 后,该字符串又与候选人 55 的姓名匹配。由于存在多个候选人满足“至多修改一个字符即可匹配”的条件,因此该张选票无效。

限制条件

  • 1≤N≤1001 \leq N \leq 100
  • 1≤M≤1001 \leq M \leq 100
  • 1≤∣Si∣≤101 \leq |S_i| \leq 10
  • 当 i≠ji \neq j 时,Si≠SjS_i \neq S_j。
  • 1≤∣Tj∣≤101 \leq |T_j| \leq 10
  • SiS_i 和 TjT_j 均为仅由小写英文字母组成的字符串。
  • NN 和 MM 均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页