
Visitors by region 
Totals Top 20   59 %  Unknown   15 %  Commercial   9 %  networks   5 %  Canada   3 %  Germany   2 %  Russia   2 %  China   < 1.0 %  Brazil   < 1.0 %  Educational   < 1.0 %    < 1.0 %  Poland   < 1.0 %  Ukraine   < 1.0 %  United Kingdom   < 1.0 %  Italy   < 1.0 %  France   < 1.0 %  India   < 1.0 %  Netherlands   < 1.0 %  Japan   < 1.0 %  Organization   < 1.0 %  Australia  



Michael Liut, March 28, 2019, 15:3016:30, ITB 201 
Title: Computing Lyndon Array
Abstract: All runs in a string can be computed in linear time. To do so, the LempelZiv 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 LempelZiv 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 wellknow 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. 



McMaster University 

Faculty of Engineering 

Faculty of Science 

Computing & Software 

Publication Downloads 
Error cannot find GD extension 

