SAC '22 Code Challenge 3 P5 - Chat Corrections

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.5s
Java 0.75s
Python 1.0s
Memory limit: 1G

Author:
Problem type

After being promoted from "Friend Finder" to "Chat Moderator" through nepotism, Mr. DeMello struggles to keep his chat logs civil.

Currently, he has a list of N banned words, S, and wants to check his M assigned messages for them.

Specifically, he wants to know the number of distinct banned words in each message.

Given that he also needs to teach, Mr. DeMello cannot make this program himself, so he assigns you to do it (as the diligent student you are).

Can you help him?

Constraints

Note: |a| denotes the length of string a, and the banned words and messages are case insensitive.

Each message and banned word will be only made of uppercase and lowercase letters.

It is also guaranteed that each banned word is distinct.

For all subtasks:

1 \le N \le 50\,000

1 \le |S_i| \le 25

1 \le M \le 1\,000

1 \le |M_i| \le 500

Subtask 1 [10%]

1 \le N, M, |M_i| \le 100

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line will contain N and M, the number of banned words and the number of messages.

The next N lines will contain S_i, the i^\text{th} banned word.

The next M lines will contain M_i, the i^\text{th} message to check.

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).

Output Specification

Output the number of distinct banned words for each of the M messages.

Sample Input

3 2
dO
kevInyAng
Zain
MaxIsGoingToFindZain
DoKevinyangIsKevinyang

Sample Output

1
2

Explanation for Sample Output

The first message only contains the last banned word: Zain. The second message contains the first and second banned words: dO and kevInyAng. Note that the casing is irrelevant.


Comments

There are no comments at the moment.