Hi,
Here is link to the paper http://www.ee.iastate.edu/~aluru/pub...ffixArrays.pdf
I understand most of it but cannot figure out last part of sorting of
the S array using S-Distance array. More Specifically In Step 3 of
Figure 3 why did substring 5 move up higher than substring 2?

Thank you

On Jul 2, 7:24*am, mirza2m <babar.ans...@gmail.com> wrote:
This appears to be an efficient implementation of the idea:
http://code.google.com/p/libdivsufsort/

I have found it easy to build and test.
It has a very favorable MIT style license.
It sure is nice to live in the information age.

On Jul 2, 7:24*am, mirza2m <babar.ans...@gmail.com> wrote:
It is a mistake in the paper, as you correctly point out, 2 should
come before 5. But the order within a bucket is actually unimportant,
as long as they are in the same bucked as indicated in the paper.

libdivsufsort is a good implementation of my algorithm. However, if
the linear behavior is important to you, e.g. you expect the input to
have long repeats, which results in high average lcp between the
suffixes, you may want to alter it to make it run in linear time.