Suffix arrays – a contest approach

ababc
#
 
ababc
a$
 
ababc
a@
 
abc# 
abca$ 
abca@ 
bababca$ 
babc# 
babca$ 
babca@ 
bc# 
bca$ 
bca@ 
11

---

c# 
ca$ 
ca@ 
This is where we can figure out that the solution is a sequence i..j in the array of sorted suffixes, 
with the property that it contains at least one suffix from every string, and the longest common prefix of 
the first and last suffix in the suffix is maximum, giving the solution for this problem. Other common 
substrings of the three strings would be common prefixes for some substring in the suffix array, e.g. bab 
for 
bab
abca$ 
bab
c# 
bab
ca$, or a for 
a
$ 
a
@ 
a
aababca@ 
a
ababc#. 
To find the sequence with the longest common prefix, go with two indexes, START and END, 
over the suffixes, where START goes from 1 to the number of suffixes, and END is the smallest index 
greater than START so that between START and END there are suffixes from all the three strings. In this 
way, the pair [START, END] will hit the optimal sequence [i..j]. This algorithm is linear because START 
takes N values while END is incremented at most N times. 
In order to sort the array containing all the suffixes, it is not necessary to sort the suffixes of every 
string in part and then merge them, as this would increase the complexity if implemented without any 
smart gimmicks. We can concatenate the three strings into a single one (abababca$aababc@aaababca# for 
the example above) and then sort its suffixes. 
Problem 7:
the longest palindrome (USACO training gate) 
Given a strings S of length n (n <= 20000) determine its longest substring that also is a palindrome.