The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? If no, please point out that other algorithm. If yes, are there any other easier to follow reference implementations?

  • $\begingroup$ (Try beautifying the source code from your link and narrow down what about it is too abstract (after trying to understand the parts of the paper that pertain to the implementation)). Wikipedia mentions SA-IS. $\endgroup$ – greybeard Nov 23 '15 at 6:51
  • 1
    $\begingroup$ A similar question was asked here on CSTheory. $\endgroup$ – Juho Nov 23 '15 at 7:33
  • $\begingroup$ @greybeard thanks for the suggestion to beautifying the source for the purposes of clarifying my (mis)understandings. Will do. Also that link suffix array induced sorting (SA-IS) algorithm with benchmark is a gem. SA-IS beats 4 other SA algorithms nearly every time for 22 benchmarks in terms of both time and space. $\endgroup$ – Ray Pereda Nov 29 '15 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.