Suffix arrays – a contest approach

Solution: 
For a fixed i, computing the longest palindrome that is centered in i requires the longest common 
prefix of the substring S[i..n] and the reversed S[1..i]. Merge the sorted suffixes of string S and the 
reversed string S’, then query the longest common prefix for S[i] and S’[n – i + 1] (S’[n – i + 1] = S[1..i]). 
Since this is done in O(lg n), the overall complexity is O(n lg n). The case where the searched palindromes 
have an even length is treated in an analogous way.
Problem 8: 
template (Polish Olympiad of Informatics 2004, abridged) 
For a given string A, find the smallest length of a string B so that A can be obtained by sticking 
several B’s together (when sticking them, they can overlap, but they have to match). 
Example: ababbababbabababbabababbababbaba 
12

---

Result: 8 
The minimum length B is “ababbaba” 
A can be obtained from B this way: 
ababbababbabababbabababbababbaba 
ababbaba 
ababbaba 
ababbaba 
ababbaba 
ababbaba 
Solution: 
The simplest solution uses suffix arrays a balanced tree and a max-heap. It’s obvious that the 
searched pattern is a prefix of A. Having sorted the suffixes of A, we shall add to B, step by step, one 
more ending character. At each step we keep to pointers L and R, representing the first and the last suffix 
in the array that have B as a prefix. The balanced tree will hold permanently the starting positions of the 
suffixes between L and R, and the heap will keep the distances between consecutive elements of the tree.
When inserting a new character into B, by two binary searches we get the new L’ and R’, with L 
≤
L’ and R’ 
≤
R. We must also update the tree and the heap. Introduce characters into B while the 
biggest(first) element in the heap is smaller or equal to the length of B. B’s final length offers the searched 
result. The final complexity is O(n lg n), where n is the length of A.