{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:40:40Z","timestamp":1760240440696,"version":"build-2065373602"},"reference-count":13,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present two modifications of Duval\u2019s algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length    \u03c1   , the other algorithm computes the Lyndon factorization of R in     O ( \u03c1 )     time and in constant space. It is shown by experimental results that the new variations are faster than Duval\u2019s original algorithm in many scenarios.<\/jats:p>","DOI":"10.3390\/a12060124","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T11:54:31Z","timestamp":1561118071000},"page":"124","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings"],"prefix":"10.3390","volume":"12","author":[{"given":"Sukhpal","family":"Ghuman","sequence":"first","affiliation":[{"name":"Faculty of Applied Science &amp; Technology, Sheridan College, 7899 McLaughlin Road, Brampton, ON L6Y 5H9, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Giaquinta","sequence":"additional","affiliation":[{"name":"F-Secure Corporation, P.O.B. 24, FI-00181 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2455-1985","authenticated-orcid":false,"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalto University, P.O.B. 15400, FI-00076 Aalto, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"key":"ref_1","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."},{"key":"ref_2","unstructured":"Mantaci, S., Restivo, A., Rosone, G., and Sciortino, M. (2013, January 2\u20134). Sorting suffixes of a text via its Lyndon factorization. Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic."},{"key":"ref_3","unstructured":"Gil, J.Y., and Scott, D.A. (2012). A bijective string sorting transform. arXiv."},{"key":"ref_4","unstructured":"Kufleitner, M. (September, January 31). On bijective variants of the Burrows-Wheeler transform. Proceedings of the Prague Stringology Conference 2009, Prague, Czech Republic."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF01191471","article-title":"Fast parallel Lyndon factorization with applications","volume":"28","author":"Apostolico","year":"1995","journal-title":"Math. Syst. Theory"},{"key":"ref_7","first-page":"17","article-title":"External memory algorithms for string problems","volume":"84","author":"Roh","year":"2008","journal-title":"Fundam. Inform."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.tcs.2016.03.005","article-title":"Faster Lyndon factorization algorithms for SLP and LZ78 compressed text","volume":"656","author":"Tomohiro","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","unstructured":"Furuya, I., Nakashima, Y., Tomohiro, I., Inenaga, S., Bannai, H., and Takeda, M. (2018, January 2\u20134). Lyndon Factorization of Grammar Compressed Texts Revisited. Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM 2018), Qingdao, China."},{"key":"ref_10","unstructured":"Ghuman, S.S., Giaquinta, E., and Tarhio, J. (2014, January 1\u20133). Alternative algorithms for Lyndon factorization. Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (1997). Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press.","DOI":"10.1017\/CBO9780511566097"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.ipl.2009.11.010","article-title":"Improving practical exact string matching","volume":"110","author":"Durian","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/351827.384246","article-title":"Fast and flexible string matching by combining bit-parallelism and suffix automata","volume":"5","author":"Navarro","year":"2000","journal-title":"ACM J. Exp. Algorithm"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/6\/124\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:00:18Z","timestamp":1760187618000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/6\/124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":13,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["a12060124"],"URL":"https:\/\/doi.org\/10.3390\/a12060124","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,6,21]]}}}