Longest recurring substring

This is a question about the longest recurring substring algorithm described in "Programming Pearls" of Jon Bentley. As I remember, they build a suffix array for the input string, sort the suffixes, and scan them.

开发者_Go百科

It looks like the most expensive step is sorting. If we use a comparison sort then the number of comparisons is O(N*logN), where N is the size of the input string. Since a string comparison is O(string length), then the sorting is O(N^2).

Does it make sense?

So, the algorithm is O(N^2) and O(N) in space. Can it be done better?

---

Although you can construct a suffix array from suffix tree, there's little point in that. It would eliminate the main advantage of suffix array (besides general simplicity): tiny memory consumption.

There's a simple way to sort array of suffixes in O(n*logn) time. (For this reason, it's often used in all kinds of algorithm contests as alternative to complicated suffix tries)

The basic idea is following. We'll sort suffixes in stages, and in stage i (i = 0, 1, 2, 3, ...) only first 2^i characters of each suffix are considered.

Sorting suffixes by their first character is trivial and should be no problem for you. After this ("0-th") stage, we'll have partially sorted array of suffixes and another array, containing partition of suffixes into buckets: each bucket holding suffixes with the same first symbol.

Now, imagine we've already finished stage i and deal with stage i + 1 now. We need to compare two suffixes s(t) and s(q) belonging to the same bucket. (Let s(t) be a suffix starting at position t in original string.)
Since the first 2^i characters are the same for them, we need to consider only next 2^i chars (so, the total would be 2^(i+1)). But suffix s(t) without its first 2^i symbols is s(t + 2^i). Therefore, we only need to compare s(t + 2^i) and s(q + 2^i) according to their first 2^i symbols and we already have this information from stage i.

The end. Implementing it for the first time could be a bit tricky (a good exercise too), but this is the idea. Note, that the only time when we read actual characters from original string is step 0. Then, on step i, we only use the result from step i - 1.

edit
This original paper from 1989 presents this idea with more details. (Much more details than necessary to understand it and implementation more complicated than needed, IMHO.)

---

Naive sorting would make suffix array construction O(n^2logn), not O(n^2).

However, there are ways to construct a suffix array in O(n) [a trivial way is to construct a suffix tree and convert it to a suffix array - suffix tree construction is O(n)].

I have no clue about whether one can do with less than O(n) space.