Title:  Computing Lyndon Array

Abstract: All runs in a string can be computed in linear time. To do so, the Lempel-Ziv factorization of the input string must be computed as the first step. In 2015, Banai et al. presented a different algorithm that requires first to compute the Lyndon array for a given ordering of the alphabet and its inverse. To our knowledge, it is the only algorithm not requiring the Lempel-Ziv factorization. Thus, it is important to know how hard or easy it is to compute the Lyndon array. A Lyndon array for a given string x and a given order of the alphabet is an integer array L such that L[i] = the length of the longest Lyndon substring of x starting at position i. We discuss a well-know approach based on sorting suffixes, computing the inverse of the suffix array, and applying the NSV (next smaller value) algorithm. There are several known algorithms of O(n log n) and O(n^2) worst case complexity we present; we include our novel O(n log n) algorithm as well. Then we discuss our elementary linear algorithm based on Baier’s method for sorting suffixes. We present the CPU time results of executions of some of these algorithms on a wide variety of input strings and analyze the results.