Suffix arrays – a contest approach

Solution: 
The searched subsequence is the smallest lexicographic rotation of the given array. Denote by S
i
k
the substring of length k that begins on position i. Let S
i
n
be the smallest substring of length n in the string 
obtained by concatenation. Supposing by absurd that s(i + n - 1) < n would mean that there is an i’ (i < i’ 
≤
j) so that S
i’
j – i’ + 1 
is smaller than S
i
n
. From the condition in the problem’s text, we have S
i’
j-i’+1
> S
i’
n
; but 
S
i’
n
> S
i
n
=> contradiction. 
Although there is an O(n) algorithm that would easily solve this, the method used during the 
contest by one of the authors(and that gained a maximum score) used suffix arrays, as in the previous task. 
Problem 3: 
substr (training camp 2003)
8

---

You are given a text consisting of N characters (big and small letters of the English alphabet and 
digits). A substring of this text is a subsequence of characters that appear on consecutive positions in the 
text. Given an integer K, find the length of the longest substring that appears in the text at least K times (1 
≤
N 
≤
16384). 
Solution: 
Having the text’s suffixes sorted, iterate with a variable i from 0 to N – K and compute the longest 
common prefix of suffix i and suffix i + K – 1. The biggest prefix found during this operation represents 
the problem’s solution. 
Problem 4: 
guess (training camp 2003) 
You and the Peasant play a totally uninteresting game. You have a large string and the Peasant 
asks you questions like ”does the following string is a substring of yours?” The Peasant asks you many 
questions and you have to answer as quick s you can. Because you are a programmer, you think that it 
would be better to know all the substrings that appear in your string. But before doing all this work, you 
are wondering how many distinct substrings are in your string (1 
≤
your string’s length 
≤
10 000)