Editorial for COCI '15 Contest 2 #4 Savez

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.

In order to solve this task, two things need to be noticed:

If a string $x_i$ ~x_i~ is a prefix of string $x_j$ ~x_j~, and $x_j$ ~x_j~ prefix of string $x_k$ ~x_k~, then string $x_i$ ~x_i~ is a prefix of string $x_k$ ~x_k~ $(i < j < k)$ ~(i < j < k)~.
If a string $x$ ~x~ is a suffix of string $y$ ~y~, then string $x^R$ ~x^R~ is a prefix of string $y^R$ ~y^R~, where $a^R$ ~a^R~ denotes string $a$ ~a~ written backwards.

Now it is sufficient to build a prefix tree in a slightly modified form:

The alphabet doesn't consist of $26$ ~26~ letters, but $26^2$ ~26^2~, because each pair of letters represents a single "letter".
When inserting a word in the tree, the first letter in the pair is taken from the beginning, the other from the end.
Each node stores the best solution for that "prefix" ( $1+\max(\text{node_children})$ ~1+\max(\text{node_children})~).

If we start from the end of input data, we've changed the task from expanding to contracting one of the existing strings. By doing this, we ensure that the solution takes into account the order of words from the input data. The time complexity of this solution is $\mathcal O(\text{total_length_of_words})$ .

Comments

There are no comments at the moment.