LIPIcs.ESA.2022.48.pdf
- Filesize: 0.84 MB
- 14 pages
Document
Lyndon Arrays Simplified
Author
Jonas Ellert 
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
Cite AsGet BibTex
Jonas Ellert. Lyndon Arrays Simplified. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.48
https://doi.org/10.4230/LIPIcs.ESA.2022.48
Abstract
A Lyndon word is a string that is lexicographically smaller than all of its proper suffixes (e.g., "airbus" is a Lyndon word; "amtrak" is not a Lyndon word because its suffix "ak" is lexicographically smaller than "amtrak"). The Lyndon array (sometimes called Lyndon table) identifies the longest Lyndon prefix of each suffix of a string. It is well known that the Lyndon array of a length-n string can be computed in O(n) time. However, most of the existing algorithms require the suffix array, which has theoretical and practical disadvantages. The only known algorithms that compute the Lyndon array in O(n) time without the suffix array (or similar data structures) do so in a particularly space efficient way (Bille et al., ICALP 2020), or in an online manner (Badkobeh et al., CPM 2022). Due to the additional goals of space efficiency and online computation, these algorithms are complicated in technical detail. Using the main ideas of the aforementioned algorithms, we provide a simpler and easier to understand algorithm that computes the Lyndon array in O(n) time.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Lyndon table
- Lyndon array
- Lyndon word
- nearest smaller suffixes
- lexicographical ordering
- general ordered alphabets
- combinatorial algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert, and Cyril Nicaud. Back-to-front online Lyndon forest construction. In Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 13:1-13:23, Prague, Czech Republic, June 2022. URL: https://doi.org/10.4230/LIPIcs.CPM.2022.13.
- Uwe Baier. Linear-time Suffix Sorting - A New Approach for Suffix Array Construction. In Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), pages 23:1-23:12, Tel Aviv, Israel, June 2016. URL: https://doi.org/10.4230/LIPIcs.CPM.2016.23.
- Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM J. Comput., 46(5):1501-1514, 2017. URL: https://doi.org/10.1137/15M1011032.
- Nico Bertram, Jonas Ellert, and Johannes Fischer. Lyndon words accelerate suffix sorting. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021), pages 15:1-15:13, Lisbon, Portugal (Virtual Conference), September 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.15.
- Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro, and Eva Rotenberg. Space efficient construction of Lyndon arrays in linear time. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 14:1-14:18, Saarbrücken, Germany (Virtual Conference), July 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.14.
-
Maxime Crochemore, Thierry Lecroq, and Wojciech Rytter. 125 Problems in Text Algorithms. Cambridge University Press, 2021. 334 pages.
- Jean-Pierre Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363-381, 1983. URL: https://doi.org/10.1016/0196-6774(83)90017-2.
- Jonas Ellert and Johannes Fischer. Linear time runs over general ordered alphabets. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 63:1-63:16, Glasgow, Scotland (Virtual Conference), July 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.63.
- Frantisek Franek, A. S. M. Sohidull Islam, Mohammad Sohel Rahman, and William F. Smyth. Algorithms to compute the Lyndon array. In Proceedings of the Prague Stringology Conference 2016, pages 172-184, Prague, Czech Republic, August 2016. URL: http://www.stringology.org/event/2016/p15.html.
- Frantisek Franek and Michael Liut. Algorithms to compute the Lyndon array revisited. In Proceedings of the Prague Stringology Conference 2019, pages 16-28, Prague, Czech Republic, 2019. URL: http://www.stringology.org/event/2019/p03.html.
- Frantisek Franek and Michael Liut. Computing maximal Lyndon substrings of a string. Algorithms, 13(11), 2020. URL: https://doi.org/10.3390/a13110294.
- Christophe Hohlweg and Christophe Reutenauer. Lyndon words, permutations and trees. Theor. Comput. Sci., 307(1):173-178, 2003. URL: https://doi.org/10.1016/S0304-3975(03)00099-9.
- Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino, and Guilherme P. Telles. Inducing the Lyndon array. In Proceedings of the 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), pages 138-151, Segovia, Spain, October 2019. URL: https://doi.org/10.1007/978-3-030-32686-9_10.
- Glenn Manacher. A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string. Journal of the ACM, 22(3):346-351, 1975. URL: https://doi.org/10.1145/321892.321896.
- Udi Manber and Gene Myers. Suffix arrays: a new method for on-line string searches. In Proceedings of the First Annual Symposium on Discrete Algorithms (SODA 1990), pages 319-327, San Francisco, California, USA, January 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320218.
- Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Grammar-compressed self-index with Lyndon words. CoRR, abs/2004.05309, 2020. URL: http://arxiv.org/abs/2004.05309.