Editorial for SAC '22 Code Challenge 3 P5 - Chat Corrections

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

Subtask 1

It suffices to iterate through all banned words and check if they are contained inside the message.

Time Complexity: \mathcal O(N|S_i|M|M_i|)

Subtask 2

Observe that we do not need to check all substrings of a message since any substring longer than the max length of a banned word cannot be a banned word. Subsequently, for each substring of each message with a length up to the longest banned word, check all substrings of the message. We can then check if this word is banned.

However, to speed this up, we can use a rolling hash. Hash all the banned words and use a rolling hash to compute the hash of all substrings of the message of a given length in \mathcal O(1). Note that you should only count banned words once per message.

Time Complexity: \mathcal O(\max(|S_i|)M|M_i|)


There are no comments at the moment.