Feature request? about libsais HOT 2 CLOSED

The libsais library is based on induced sorting SAIS algorithm. Unfortunately this algorithm could not support partial suffix array construction. Some other algorithms (like DC3) might be able to support it, but this is outside of scope for the libsais library.

from libsais.

Let me reply to this question just so that if anyone has a similar need.

It seems a direct solution is difficult, I haven't seen a fast implementation that's easily adpatable to my need. Finally, I have to sort the whole thing and only keep the n-th position. It's possible that slower implementations can do this directly but I doubt it will be faster overall.

If you can live with an approximate result like me, I ended up breaking the input into equal chunks and sort the resulting equal-length strings, a simple qsort/std::sort will be fast enough, and there's also a whole bunch of fast implementations like https://github.com/bingmann/parallel-string-sorting

from libsais.