Editorial for WC '16 Contest 1 J2 - Frankenstein's Monster


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.

An important skill in solving problems like this one is interpreting the statement. The most important part of the statement is this:

A "word" is a maximal consecutive sequence of non-period characters in the string. That is, each word is either preceded by a period or is at the start of the string. Similarly, each word is followed by a period or is at the end of the string.

This means that we should replace all substrings Frankenstein with Frankenstein's.Monster if and only if one of the following is true:

  • it's at the beginning of S (always followed by a period, except when it's also at the end of S)
  • it's both preceded and followed by a period
  • it's at the end of S (always preceded by a period, except when it's also at the beginning of S)

We can solve this by finding all substrings Frankenstein and checking all these cases. Alternatively, this problem becomes a bit simpler if we start by augmenting the given string, adding one . to the start and another . to the end (we just have to remember to remove these at the end before outputting the answer). We then want to replace every occurrence of .Frankenstein. with .Frankenstein's.monster.. To find each occurrence, some programming languages provide a built-in function to search for a substring within a string. Alternatively, this can be done by looping over every character in the string and checking if the 14-character substring starting there is equal to .Frankenstein.. Once an occurrence is found starting at index i, one way to replace it is to replace the whole string S with the concatenation of substrings S[1 \dots (i-1)] + .Frankenstein's.monster. + S[(i+14) \dots |S|] where |S| is the length of S.


Comments

There are no comments at the moment.