PROBLEM LINK:
Author: Minako Kojima
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
Medium
PREREQUISITES:
Suffix Array, LCP Array, Persistent Segment Tree
PROBLEM:
Given a string S, support the following queries:
- Given integers k1 and k2, compute the k1-th lexicographic smallest substring S1 among all unique substrings of S. The substring S1 may occur several times in S, find its k2-th occurrence.
- Given a substring S[l…r], find its rank k1 among the unique substrings of S, Also this substring may occur several times in the string, find how many of these substrings start before l.
EXPLANATION:
First let us ignore the k2, and instead consider a simpler problem, which supports the following two queries:
- Given k1, find the k1-th lexicographic smallest substring S1 among all unique substrings of S.
- Given a substring S[l…r], find its rank k1 among the unique substrings of S.
The two queries can be answered easily using the suffix array and lcp array of the string S. In order to see the construction algorithm for suffix and lcp array consider looking at this.
Briefly, suffix array of an string S[1…N], consists of of an array SA[1…N], where SA[i] is the index x such that S[x…N] is the i-th lexicographically smallest suffix of string S. Usually, we also create the inverse array of SA, known as POS[1…N]. The element POS[i] gives the rank of suffix S[i…N] among all suffixes of S.
the lcp array lcp[1…N] is used to compute the longest common prefix of suffixes of S. The value lcp[i] represents the length of the longest common prefix of the suffix S[SA[i]…N] and S[SA[i - 1]…N] for i > 1. A combination of lcp array and range minimum data structure can be used to compute the length of the common prefix of arbitrary suffixes of S in O(1) time as shown here.
Unique Substrings:
Suffix array can be used to compute the number of unique substrings of S. We count these substrings in lexicographic order. Since the array SA[] consist of the string indices in lexicographic order of suffixes, hence, in the lexicographic enumeration of unique substrings of S, the substrings starting at SA[i] will be counted before counting the substrings starting at SA[j] for i < j.
Suppose we are considering the substrings starting at index SA[i]. There are (N + 1 - SA[i]) such substrings, however, many of these substrings have already been counted. More specifically, if the length of the longest common prefix of suffix starting at index SA[i] and the suffix starting at SA[i - 1] is x, then x of these (N + 1 - SA[i]) substrings have already been counted. So the number of additional substrings will be (N + 1 - SA[i] - x) = (N + 1 - SA[i] - lcp[i]).
Adding these values together will give us the number of unique substrings of S. Now, let us create an array substr[1…N], such that substr[i] gives the number of unique substrings that have been counted after considering the suffixes starting at SA[1], SA[2], …, SA[i].
substr[1] = N + 1 - SA[1],
substr[i] = substr[i - 1] + N + 1 - SA[i] - lcp[i]
Using the array substr[], we can compute the k1-th lexicographic smallest substring easily. Basically, we perform a binary search for k1 in the array substr[]. Let us say substr[i - 1] < k1 <= substr[i], this means the k1-th smallest substring must start at SA[i]. More specifically, the substring will be S[l…r], where,
l = SA[i]
r = SA[i] + lcp[i] + k1 - substr[i - 1]
On the other hand, if we want to compute the rank of substring S[l…r], we need to find out when this substring was considered in the enumeration of unique substrings. Suppose this string was counted for the first time when we were considering the substrings starting at SA[x], that means x is the smallest index such that the suffix starting at SA[x] contains S[l…r] as a prefix, i.e., the the length of the longest common prefix of the suffix starting at l and SA[x] is >= (r - l + 1).
Since the suffix starting at index l contains the substring S[l…r] as a prefix, x must not exceed POS[l]. Moreover, for all x <= y <= POS[l], the length of the longest common prefix between the suffix starting at SA[y] and the suffix starting at l will be >= (r - l + 1). Hence, x can be found using a binary search.
Once we have found x, the rank k1 can be found easily. In fact the rank k1 will be
k1 = substr[x - 1] + (r - l + 1) - lcp[x]
This means using the suffix and lcp array, we can handle the simplified queries in O (lg N) time. Next, we discuss how to handle the queries which also consider the ranking of same substring based on their starting points.
Ranking of Substrings based on Starting Index:
Suppose that we are handling the first query, where k1 and k2 are given and we want to compute the substring S[l…r]. Using the algorithm described in previous section, we can easily find one occurrence of this substring, which is at
l = SA[i]
r = SA[i] + lcp[i] + k1 - substr[i - 1]
where i is the smallest index such that substr[i] >= k1.
Note that the substring S[l…r], will occur at position x, iff the length of the longest common prefix of the suffix starting at x and the suffix starting at l is >= (r - l + 1). We need to find all such x’s. It can be seen that the set of these x’s will be of the form
{SA[low], SA[low + 1], …, SA[i], …, SA[high - 1], SA[high]}
The value of low and high can be computed using binary search and the lcp computation. Once, we have the set of all possible x’s, we need to find the k2-th smallest value among these. We will discuss how to do this efficiently a bit later. First let us discuss how to handle the second type of query.
For the second query, we are given the substring S[l…r]. Using the method described in previous section, we can compute its rank k1 in O (lg N) time. This substring will occur many times in the string, and the starting indices of these occurrence will form the set
{SA[low], SA[low + 1], …, SA[POS[l]], …, SA[high - 1], SA[high]}.
Here also the value of low and high can be computed using a binary search, and we want to compute the rank of SA[POS[l]] in this set, which will be the value of k2.
Persistent Segment Tree:
In the above section we have seen that the problem of handling the two kind of queries finally reduces to design a data structure that supports rank and select queries on the subarray. More specifically,
Given an array SA[1…N], design a data structure structure that supports the following queries:
- Given l, r, and k find the k-th smallest element in the subarray SA[l…r]
- Given l, r, and x, find the rank of x in the subarray SA[l…r].
The data structure that handles these queries efficiently is known as Persistent Segment Tree, which can handle the two queries in O (lg N) time. The details of this data structure can be seen at here and here (in Russian, I guess).
Hence, we can handle the two kind of queries in O (lg N) time.
Time Complexity:
Preprocessing time: O (N lg N)
Query time: O (lg N)
Weak Test Cases:
Unfortunately, the test cases for this problem were weak (or the time limit was too relaxed), that allowed O (QN) solutions to run in time. Some contestants informed the admins about this during the contest, however, those mails slipped through the cracks, and the setter never became aware of this issue during the contest. The setter has now added the strong test cases, which are available in practice section. However, at this point it does not seem possible to rejudge all accepted solutions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.
