TASUFFIX - Editorial

Problem Link:

Practice

Contest

Difficulty:

Hard

Pre-requisites:

Splay Trees

Problem:

Given a suffix array, find the number of strings that correpond to it. The suffix array can be obtained by applying some operations(see problem for details).

Explanation:

The problem can be broken into two parts:

  • Constructing the suffix array from queries.
  • Given the suffix array, find the number of strings that correspond to it.

We will first solve the easy part, finding number of strings.

Given a Suffix Array find number of strings

Let the suffix array be a1, a2, … an.
Let S be an arbitrary string corresponding to the given suffix array.
Let
     S[i] = ith character of the string
     Suffix[i] = suffix of S starting from ith character.

We must have

S[a1] ≤ S[a2] ≤ S[a3] … ≤ S[an]          -  (1)

Also, by our definition of “string”, if S[ai] < S[ai+1], then S[ai+1] = S[ai] + 1.

Therefore, if we replace each ‘≤’ by exactly one out of ‘=’ and ‘<’, we will get a unique string.

Also, if each ‘≤’ had full “freedom” of choosing exactly one out of ‘<’ and ‘=’, then number of strings for a given suffix array would be 2n-1.

However, world is not such a nice place. Any ‘≤’ can always be replaced by ‘<’, but it might not possible to replace it by ‘=’. So lets try to see when a ‘≤’ cannot be replaced by ‘=’.

Consider an arbitrary ‘≤’, S[ai] ≤ S[ai+1], and lets see what happens when we replace it by ‘=’.

By suffix array condition, we have

Suffix[ai] < Suffix[ai+1].
But                        S[ai] = S[ai+1]
So, we should have Suffix[ai+1] < Suffix[ai+1+1]

Therefore, the ‘≤’ between S[ai] and S[ai+1] can be replaced by ‘=’ iff ai+1 appears before ai+1+1 in the suffix array. The answer will be 2k where
       k = no of positions i such that ai+1 appears before ai+1+1 in the suffix array

  • To handle the case where ai = N or ai+1 = N, we can append(conceptually) ‘0’ to the of string, and rewrite the suffix array as
                n+1, a1, a2, … an

  • Since the suffix array is very large, we will actually obtain it in the form:
                (x1, y1), (x2, y2), … (xk, yk)
    Where each (xi, yi) represents an AP starting at xi, ending at yi, with common difference ±1.
    It can be verified if both ai and ai+1 are not boundary of some contiguous segment(i.e. do not belong to the set { x1, y1, x2, y2, … xk, yk }), then ai+1 appears before ai+1+1. So, we have to only check at boundaries of segments, which are O(k) in number.
    It is non trivial to find the position of ai+1 's. However, to check the order of two arbitrary elements in suffix array, we only need to check

    1. If they belong to same contiguous segment, then what is their order in the segment.
    2. If they belong to different segments, then what is the order of those segments.

This can be done using STL’s map data structure as m[xi] = m[yi] = i, and using lower_bound to locate the relative position of segments in which they lie.

Obtaining the suffix array

We need to implement the two operations : flip ranges and move ranges to front.
This can be done using balanced binary trees(splay trees). Each node in the tree will store a range of consecutive numbers from u to v (u may larger than v).
At the beginning our tree contains only single node which is (1, n).
At any time, the nodes of the tree form a disjoin partition of the range (1,n).
Every node has:

  • int u, v: indicate the range(u, v).
  • int num: the subtree rooted at this node has total of num array elements.
  • bool flip: the entire subtree rooted at this node is flipped. This will be propagated down in lazy manner.

A flip-range, or move-range-to-front operation may need to split at most 2 nodes(for beginning and end of operation’s range), so do that first.
Use splay operation to obtain a subtree that corresponds to the given range.

  1. Flip operation: Flip that range by updating flip flag on the node.
  2. Move the range to front: Can be done by shuffling O(1) nodes of the tree.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

3 Likes