## Editorial for Tree of Life

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.

Author: r3mark

For the first subtask, the longest common substring of two DNA sequences is simply the minimum of their lengths. Note that two nodes and are distant if and only if there is a node with two distinct children such that is in the subtree of one of the children and is in the subtree of the other. We can use simple tree DP to determine the answer.

Time Complexity:

For the second subtask, there were several different solutions. The majority of them were based around binary searching for the answer. This editorial will outline a different approach.

Consider the suffix array of the concatenation of the strings. We use the following algorithm:

Keep a left pointer and a right pointer. There are two states: either the left pointer is fixed or the right pointer is fixed. Initially, the left pointer is fixed.

When the left pointer is fixed, keep moving the right pointer until the node corresponding to the suffix at the right pointer is not an ancestor of the node corresponding to the suffix at the left pointer. Once this happens, the right pointer is now fixed.

When the right pointer is fixed, keep moving the left pointer until it reaches the right pointer. Once this happens, the left pointer is now fixed.

Throughout these steps, check whether or not the two nodes being pointed at are distant and compute the LCP of the two suffixes being considered. This algorithm is guaranteed to find the answer. The proof of this is left to the reader.

Time Complexity:

• commented on Jan. 3, 2018, 6:21 a.m. edited

There is another solution with hash that is very easy.

• commented on Jan. 3, 2018, 6:27 a.m.

I used the same. The hash+ Binary search solution was a lot more simple and easy.

• commented on Jan. 3, 2018, 2:30 a.m.

There is another relatively simple solution with suffix automaton.

• commented on Jan. 3, 2018, 6:10 a.m.

The idea is that when we have two strings, we can easily find their LCS with suffix automaton (look at the last paragraph of http://e-maxx.ru/algo/suffix_automata). For more than 2 strings you can merge them like S1 $S2$ ... $Sk-1$ Sk and preform the same thing as said in e-maxx.
In my solution I've used a generalized suffix automaton as a replacement of "S1 $S2$ ... $Sk-1$ Sk" but both will result in time complexity. I'm not sure if it's against the rules or not to post a link to my submission (If it is I'll remove it) but you can find it here.