The linear equivalence of the suffix array and the partially sorted Lyndon array

In 2015 Uwe Baier presented a linear-time algorithm that directly sorts the suffixes of a string, the first such algorithm that is not recursive. In fact, his approach implicitly gives quite a bit more: it includes a linear-time elementary algorithm for computing what turns out to be a partially sorted version of the Lyndon array, and then shows how this can be used to sort the suffixes. At the same time, it is known that the Lyndon array can be computed in linear time from the suffix array. This paper extends these aspects of Baier’s work to establish the linear equivalence of certain orderings of maximal Lyndon substrings and of fully sorted suffixes. By this terminology we mean that each data structure can be transformed into the other by a simple linear-time computation.