This problem is solved with such a data structure as a suffix automaton. Almost all AC solutions used the suffix automaton/tree data structure and had the following idea or someting very similar:
We have to build a suffix automaton on the given tree. If we have already built the suffix automaton on a tree, then the problem becomes quite standard:
Now, how to build the suffix automaton on a tree:
Let's see how some standard building algorithm works. We have some states, each state corresponds to some set of strings and all the strings in one state are actually suffixes of some string. In the building algo we try to add the letters one-by-one to the previous state e.g. when we add the i-th letter, we try to add it to the state that corresponds to the (i-1) first letters of the string. But as we can see, transitions from any state by some letter (when we append it to some state) don't depend on the transitions by other letters. So we can add not the only one (as in the standard algo), but several transitions from one state. Thus, to build the suffix automaton on a tree we only have to store the state that corresponds to the path from the root to the vertex. Then we can simply add a transition from the parent of some vertex to its son. The only (and obvious) requirement is that for every vertex before adding it we have to add its parent first. So, we have to "extend" our tree in a BFS or DFS order.
The writer's implementation of such a solution worked for ~2 sec. on a single test case. There were a few solutions with another idea that produced correct answers but almost all of them got TLE during the contest. Generally, the TL was equal to 2*authors solution runtime.
Can be found here.
Can be found here.
This question is marked "community wiki".
asked 12 Nov '12, 13:49
So, what is the complexity of this algorithm?..
answered 17 Jan '15, 18:05