Editorial for DMOPC '15 Contest 5 P2 - D-Mails


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.

The problem is asking us to check if each tagline is a subsequence of each of the messages. The simplest approach is a two-pointer solution. We use one pointer to keep track of the subsequence we have so far and the other to iterate through the message itself. We can then write this as a function and check the members in order of seniority, using a boolean value to indicate if we have already found a match.

Time Complexity: \mathcal{O}(N \times (\max(|S|)+\max(|T|)))


Comments

There are no comments at the moment.