Editorial for WC '17 Finals J2 - Redundant Formations


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.

Our overall approach should be to consider each possible substring of S, check whether or not it's redundant, assemble a list of distinct substrings which are, and output the number of substrings in this list at the end.

We can do so by iterating over all pairs of indices (i, j), such that 1 \le i < j \le |S|. Each such pair corresponds to the substring S_{i \dots j}, with a length of L = j-i+1. We can then consider each index k between i+1 and j (inclusive), and check if the substring S_{k \dots (k+L-1)} is equal to S_{i \dots j} (note that k should also be capped at |S|-L+1 to avoid considering substrings which would go past the end of S). If such an index k is found, then a pair of overlapping equal substrings has also been found, meaning that S_{i \dots j} must be redundant.

What remains is maintaining the list of distinct redundant substrings, and being able to add S_{i \dots j} to it if not already present. One option is to maintain this list as an array, and loop over all of its existing entries to check if S_{i \dots j} is equal to any of them. A more elegant option is to use a built-in data structure such as a C++ set, which will automatically ensure that its entries are all distinct.

The time complexity of the solution described above is \mathcal O(N^4), which is comfortably fast enough, though it's also possible to optimize it to \mathcal O(N^3).


Comments

There are no comments at the moment.