LRS and t-tuple estimates can be dramatically faster using different algorithms

If you use a suffix array / longest common prefix array (SA / LCP arrays), you can calculate these estimates in quadratic time. Indeed, this process is practically very fast if you use optimized implementations of modern algorithms (e.g., https://github.com/y-256/libdivsufsort)

See the last three pages of our implementation comments:
https://bit.ly/UL90BCOM