TASUFFIX - Editorial

utkarsh_lath · July 22, 2013, 12:00am

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 a₁, a₂, … a_n.
Let S be an arbitrary string corresponding to the given suffix array.
Let
S[i] = i^th character of the string
Suffix[i] = suffix of S starting from i^th character.

We must have

S[a₁] ≤ S[a₂] ≤ S[a₃] … ≤ S[a_n] - (1)

Also, by our definition of “string”, if S[a_i] < S[a_i+1], then S[a_i+1] = S[a_i] + 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 2^n-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[a_i] ≤ S[a_i+1], and lets see what happens when we replace it by ‘=’.

By suffix array condition, we have

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

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

To handle the case where a_i = N or a_i+1 = N, we can append(conceptually) ‘0’ to the of string, and rewrite the suffix array as
n+1, a₁, a₂, … a_n
Since the suffix array is very large, we will actually obtain it in the form:
(x₁, y₁), (x₂, y₂), … (x_k, y_k)
Where each (x_i, y_i) represents an AP starting at x_i, ending at y_i, with common difference ±1.
It can be verified if both a_i and a_i+1 are not boundary of some contiguous segment(i.e. do not belong to the set { x₁, y₁, x₂, y₂, … x_k, y_k }), then a_i+1 appears before a_i+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 a_i+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[x_i] = m[y_i] = 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.

Flip operation: Flip that range by updating flip flag on the node.
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