{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:23:54Z","timestamp":1772252634437,"version":"3.50.1"},"reference-count":37,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T00:00:00Z","timestamp":1605139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN\/5504-2018"],"award-info":[{"award-number":["RGPIN\/5504-2018"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>There are two reasons to have an efficient algorithm for identifying all right-maximal Lyndon substrings of a string: firstly, Bannai et al. introduced in 2015 a linear algorithm to compute all runs of a string that relies on knowing all right-maximal Lyndon substrings of the input string, and secondly, Franek et al. showed in 2017 a linear equivalence of sorting suffixes and sorting right-maximal Lyndon substrings of a string, inspired by a novel suffix sorting algorithm of Baier. In 2016, Franek et al. presented a brief overview of algorithms for computing the Lyndon array that encodes the knowledge of right-maximal Lyndon substrings of the input string. Among those presented were two well-known algorithms for computing the Lyndon array: a quadratic in-place algorithm based on the iterated Duval algorithm for Lyndon factorization and a linear algorithmic scheme based on linear suffix sorting, computing the inverse suffix array, and applying to it the next smaller value algorithm. Duval\u2019s algorithm works for strings over any ordered alphabet, while for linear suffix sorting, a constant or an integer alphabet is required. The authors at that time were not aware of Baier\u2019s algorithm. In 2017, our research group proposed a novel algorithm for the Lyndon array. Though the proposed algorithm is linear in the average case and has O(nlog(n)) worst-case complexity, it is interesting as it emulates the fast Fourier algorithm\u2019s recursive approach and introduces \u03c4-reduction, which might be of independent interest. In 2018, we presented a linear algorithm to compute the Lyndon array of a string inspired by Phase I of Baier\u2019s algorithm for suffix sorting. This paper presents the theoretical analysis of these two algorithms and provides empirical comparisons of both of their C++ implementations with respect to the iterated Duval algorithm.<\/jats:p>","DOI":"10.3390\/a13110294","type":"journal-article","created":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T10:00:32Z","timestamp":1605175232000},"page":"294","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Maximal Lyndon Substrings of a String"],"prefix":"10.3390","volume":"13","author":[{"given":"Frantisek","family":"Franek","sequence":"first","affiliation":[{"name":"Department of Computing and Software, McMaster University, Hamilton, ON L8S 4K1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2965-5302","authenticated-orcid":false,"given":"Michael","family":"Liut","sequence":"additional","affiliation":[{"name":"Department of Mathematical and Computational Sciences, University of Toronto Mississauga, Mississauga, ON L5L 1C6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,12]]},"reference":[{"key":"ref_1","first-page":"329","article-title":"On Burnside\u2019s Problem. II","volume":"78","author":"Lyndon","year":"1955","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/s00453-015-0065-z","article-title":"2D Lyndon words and applications","volume":"77","author":"Marcus","year":"2017","journal-title":"Algorithmica"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1016\/j.ejc.2005.07.019","article-title":"The origins of combinatorics on words","volume":"28","author":"Berstel","year":"2007","journal-title":"Eur. J. Comb."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.2307\/1970044","article-title":"Free differential calculus IV. The quotient groups of the lower central series","volume":"68","author":"Chen","year":"1958","journal-title":"Ann. Math. 2nd Ser."},{"key":"ref_5","first-page":"358","article-title":"Irreducible polynomials, synchronizing codes, primitive necklaces and cyclotomic algebra","volume":"4","author":"Golomb","year":"1967","journal-title":"Comb. Math. Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/jagm.2001.1158","article-title":"The complete analysis of a polynomial factorization algorithm over finite fields","volume":"40","author":"Flajolet","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF02679619","article-title":"Smallest components in decomposable structures:exp-log class","volume":"29","author":"Panario","year":"2001","journal-title":"Algorithmica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","article-title":"Factorizing words over an ordered alphabet","volume":"4","author":"Duval","year":"1983","journal-title":"J. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/0304-3975(94)00013-1","article-title":"Average cost of Duval\u2019s algorithm for generating Lyndon words","volume":"132","author":"Berstel","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(78)90002-X","article-title":"Necklaces of beads in k colors and k-ary de Bruijn sequences","volume":"23","author":"Fredricksen","year":"1983","journal-title":"Discret. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1137\/15M1011032","article-title":"The \u201cRuns\u201d Theorem","volume":"46","author":"Bannai","year":"2017","journal-title":"SIAM J. Comput."},{"key":"ref_12","unstructured":"Franek, F., Paracha, A., and Smyth, W. (2017, January 28\u201330). The linear equivalence of the suffix array and the partially sorted Lyndon array. Proceedings of the Prague Stringology Conference, Prague, Czech Republic."},{"key":"ref_13","unstructured":"Baier, U. (2015). Linear-Time Suffix Sorting\u2014A New Approach for Suffix Array Construction. [Master\u2019s Thesis, University of Ulm]."},{"key":"ref_14","first-page":"1","article-title":"Linear-Time Suffix Sorting\u2014A New Approach for Suffix Array Construction","volume":"Volume 54","author":"Grossi","year":"2016","journal-title":"Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/s11786-007-0024-4","article-title":"Lempel-Ziv factorization using less time & space","volume":"1","author":"Chen","year":"2013","journal-title":"Math. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Ilie, L., and Smyth, W. (2008, January 25\u201327). A simple algorithm for computing the Lempel-Ziv factorization. Proceedings of the 18th Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2008.36"},{"key":"ref_17","unstructured":"Kosolobov, D. (2015, January 4\u20137). Lempel-Ziv factorization may be harder than computing all runs. Proceedings of the 32 International Symposium on Theoretical Aspects of Computer Science\u2014STACS 2015, Garching, Germany."},{"key":"ref_18","unstructured":"Digelmann, C. Personal communication."},{"key":"ref_19","unstructured":"Franek, F., Sohidull Islam, A., Sohel Rahman, M., and Smyth, W. (2016, January 29\u201331). Algorithms to compute the Lyndon array. Proceedings of the Prague Stringology Conference 2016, Prague, Czech Republic."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0304-3975(03)00099-9","article-title":"Lyndon words, permutations and trees","volume":"307","author":"Hohlweg","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., and Chan, W.H. (2009, January 16\u201318). Linear suffix array construction by almost pure induced-sorting. Proceedings of the 2009 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2009.42"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jda.2018.08.001","article-title":"Lyndon array construction during Burrows\u2013Wheeler inversion","volume":"50","author":"Louza","year":"2018","journal-title":"J. Discret. Algorithms"},{"key":"ref_23","unstructured":"Franek, F., Liut, M., and Smyth, W. (2018, January 27\u201328). On Baier\u2019s sort of maximal Lyndon substrings. Proceedings of the Prague Stringology Conference 2018, Prague, Czech Republic."},{"key":"ref_24","unstructured":"(2020, November 03). C++ Code for IDLA, TRLA and BSLA Algorithms. Available online: https:\/\/github.com\/MichaelLiut\/Computing-LyndonArray."},{"key":"ref_25","unstructured":"Farach, M. (1997, January 20\u201322). Optimal suffix tree construction with large alphabets. Proceedings of the 38th IEEE Symp. Foundations of Computer Science, Miami Beach, FL, USA."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2493175.2493180","article-title":"Practical linear-time O(1)-workspace suffix sorting for constant alphabets","volume":"31","author":"Nong","year":"2013","journal-title":"ACM Trans. Inf. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","article-title":"An algorithm for the machine calculation of complex Fourier series","volume":"19","author":"Cooley","year":"1965","journal-title":"Math. Comput."},{"key":"ref_28","unstructured":"Franek, F., and Liut, M. (2019, March 01). Computing Maximal Lyndon Substrings of a String, AdvOL Report 2019\/2, McMaster University. Available online: http:\/\/optlab.mcmaster.ca\/\/component\/option,com_docman\/task,cat_view\/gid,77\/Itemid,92."},{"key":"ref_29","unstructured":"Franek, F., and Liut, M. (2019, January 26\u201328). Algorithms to compute the Lyndon array revisited. Proceedings of the Prague Stringology Conference 2019, Prague, Czech Republic."},{"key":"ref_30","unstructured":"Liut, M. (2019). Computing Lyndon Arrays. [Ph.D. Thesis, McMaster University]."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2003). Combinatorics on Words, Cambridge University Press.","DOI":"10.1017\/CBO9781107326019"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2005). Applied Combinatorics on Words, Cambridge University Press.","DOI":"10.1017\/CBO9781107341005"},{"key":"ref_33","unstructured":"Smyth, B. (2003). Computing Patterns in Strings, Pearson Addison-Wesley."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Louza, F., Gog, S., and Telles, G. (2020). Construction of Fundamental Data Structures for Strings, Springer.","DOI":"10.1007\/978-3-030-55108-7"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Burkhardt, S., and K\u00e4rkk\u00e4inen, J. (2003, January 25\u201327). Fast Lightweight Suffix Array Construction and Checking. Proceedings of the 14th Annual Conference on Combinatorial Pattern Matching, Michoacan, Mexico.","DOI":"10.1007\/3-540-44888-8_5"},{"key":"ref_36","unstructured":"Paracha, A. (2017). Lyndon Factors and Periodicities in Strings. [Ph.D. Thesis, McMaster University]."},{"key":"ref_37","unstructured":"K\u00e4rkk\u00e4inen, J., and Sanders, P. (July, January 30). Simple linear work suffix array construction. Proceedings of the 30th International Conference on Automata, Languages and Programming, Eindhoven, The Netherlands."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/294\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:32:40Z","timestamp":1760178760000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,12]]},"references-count":37,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["a13110294"],"URL":"https:\/\/doi.org\/10.3390\/a13110294","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202009.0557.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,12]]}}}