Suffix arrays – a contest approach

 
3 Applications in contest problems 
 
We tried to gather as many problems as possible that can be solved using the suffix arrays. Going 
through all the problems at the first reading would seem rather difficult for a reader who had the first 
contact with suffix arrays by reading this paper. To make the lecture easier, the problems are arranged in 
an increasing difficulty order. 
7

---

Task 1:
hidden password (ACM 2003, abridged) 
Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. 
For example, the rotations of the string “alabala” are: 
alabala 
labalaa 
abalaal 
balaala 
alaalab 
laalaba 
aalabal 
and the smallest among them is “aalabal”. 
Solution: 
Usually, when having to handle problems that involve string rotations, one would rather 
concatenate the string with itself in order to simplify the task. After, the minimal sequence of length n is 
requested. As their order is determined by the order of the string’s suffixes – although there is a linear 
solution presented in [10]- suffix arrays are one easy gimmick that can solve the problem instantly. 
Problem 2: 
array (training camp 2004)
Consider an array c
1
c
2
...c
n
consisting of n(1 
≤
n 
≤
30 000)) elements from the set {A, B}. 
Concatenate the array with itself and obtain an array of length 2n. For an index k (1
≤
k
≤
2n) consider the 
subsequences of length at most n that end on position k, and among these let s(k) be the smallest 
lexicographic subsequence. Determine the index k for which s(k) is longest. Hint: Let X and Y bet two 
arrays as defined previously and « o » the concatenation operator. In this problem you will consider that X 
> X o Y.