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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
It suffices to iterate through all banned words and check if they are contained inside the message.
Time Complexity:
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 . Note that you should only count banned words once per message.
Time Complexity:
Comments