Problem Link:Difficulty:Hard Prerequisites:Suffixtrees Problem:Start with an empty string, and do the following operations: Explanation:This was easily the hardest problem. The setters solution was based on Ukkonen's Algorithm. The time complexity is O(Q). Ukkonen's algorithm has been described very neatly on stackoverflow. It has also been described in short in these slides. I would recommend reading the stackoverflow post(if possible, the slides as well) before we continue. Here is link to the published paper for the enthusiasts. It can also be found on emaxx.ru. The sum of length of all edges of the suffix tree is equal to the number of distinct substrings in the string. So, If we had to merely append characters to the end of string, it can be easily done with Ukkonen itself, because we could maintain sum of length of all edges. We also need to maintain the number of leaves, because the length of each leaf edge increases by one after each step. Length of remaining edges remain same, unless the edge has been split in previous step. Ukkonen's algorithm can be modified to handle deletions as well, and its not too hard to figure out. Here are the details. The first step is to realize that each leaf corresponds to a unique suffix of the string, and we can do bookkeeping to maintain the leaves for each suffix. Only those suffixes whose length is equal to remainder(refer to stackoverflow article) or less have no leaves corresponding to them. The algorithm will automatically ensure that we remove only those suffixes for which a leaf exists. Due to bookkeeping, we can get hold of the leaf corresponding to the current string. We only need to remove this leaf. We also might need to remove some internal edges that were being used only by the suffix we are removing. To see this, consider the suffix tree for string "aaac". Suppose we remove the first 'a' from string now. We would just need to remove corresponding leaf(i.e. node 3). Now suppose we were to remove the second 'a' as well. Then we would need to remove vertex 4, as well as vertex 2, because the 12 edge is being used only by this suffix. In general, when removing a leaf, keep removing its parent as well if To see the reason for point 2 above, consider the string "aaacaac". The active node after adding last 'c' will be node 2. Now lets say, you remove the first 'a' from the beginning. After that your suffix tree looks like: Now you also want to delete the second 'a'. However, you cannot remove node 2, because the node 2 may have outdegree 0, but it is being used by the active suffix. After removal of node 4, our suffix tree looks as follows. Acrush and few others used suffix arrays and LCP array with high large amount of optimizations to pass the time limit. Setter's Solution:Can be found here Tester's Solution:Can be found here Editorialist's Solution:Can be found here
This question is marked "community wiki".
asked 16 Sep '13, 15:13
showing 5 of 6
show all

We can solve this problem by Suffix Array in O(nlogn) time.
We create a segtree to maintain the suffix, rules are:
Let's talk about the two operations
Then the problem is solved. A good implementation is needed to avoid TLE. answered 16 Sep '13, 18:57
I got AC this way. http://www.codechef.com/viewsolution/2659824
(16 Sep '13, 19:00)
This is essentially my solution, too. But I needed to obtain the LCP of two suffixes in O(1) time (by using O(1) RMQ queries) in order to avoid TLE.
(16 Sep '13, 22:01)
@mugurelionut I used segtree to perform rmq query and also got AC. The slowest part is maintain RemL, RemR, sum and cnt while inserting or deleting a suffix. I try to reduce "updates per operation" and got AC.
(17 Sep '13, 06:50)

can someone describe the suffix array solution, i'm having trouble trying to understand ACRush solution, does it suppose to work in (n^2) at worst case ?
At the beginning of the editorial the difficulty of this problem is written as "Medium", instead of "Hard" (as its label suggests, and as it is obvious to most of us). Is this a mistake or is there any other reason for considering it of "Medium" difficulty?
Well, fixed now.
@mugurelionut i'm also thinking of the same thing.
how can this problem be solved by Suffix Automaton?
Could someone provide sample input and output so we can test our code for correctness?