You are not logged in. Please login at www.codechef.com to post your questions!

×

TSUBSTR - Editorial

1
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

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:
1. Count the number of paths in a directed acyclic graph
2. Find the K-th path in a directed acyclic graph
It can be solved, for example, with a topological sort and a DP F[i] - the number of paths that begin in the vertex i. Obviously, F[i] is the sum of all F[x] such that there is an edge from i to x, plus one (to count the empty string too). Then, the answer to the first question is F[root] where root is the state that corresponds to the empty string. To answer the queries we can use a quite standard method: start from the empty string and then iterate through the letters of the alphabetical order in order that they are given to find the first letter. Then we can change our state and iterate again to find the second letter, etc.

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.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Nov '12, 13:49

admin's gravatar image

0★admin ♦♦
17.4k347487515
accept rate: 36%


So, what is the complexity of this algorithm?..

link

answered 17 Jan '15, 18:05

melfice's gravatar image

2★melfice
519
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,272
×872
×10
×1

question asked: 12 Nov '12, 13:49

question was seen: 4,418 times

last updated: 17 Jan '15, 18:05