{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:01:38Z","timestamp":1760234498523,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T00:00:00Z","timestamp":1621555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Japan Society for the Promotion of Science","award":["JP18F18120","JP21K17701"],"award-info":[{"award-number":["JP18F18120","JP21K17701"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present linear-time algorithms computing the reversed Lempel\u2013Ziv factorization [Kolpakov and Kucherov, TCS\u201909] within the space bounds of two different suffix tree representations. We can adapt these algorithms to compute the longest previous non-overlapping reverse factor table [Crochemore et al., JDA\u201912] within the same space but pay a multiplicative logarithmic time penalty.<\/jats:p>","DOI":"10.3390\/a14060161","type":"journal-article","created":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T13:15:15Z","timestamp":1621602915000},"page":"161","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reversed Lempel\u2013Ziv Factorization with Suffix Trees"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"first","affiliation":[{"name":"M&D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","article-title":"Searching for gapped palindromes","volume":"410","author":"Kolpakov","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textural substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.tcs.2014.01.013","article-title":"Note on the greedy parsing optimality for dictionary-based text compression","volume":"525","author":"Crochemore","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear Pattern Matching Algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973) SWAT, Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_5","unstructured":"Sugimoto, S., Tomohiro, I., Inenaga, S., Bannai, H., and Takeda, M. (2021, April 15). Computing Reversed Lempel\u2013Ziv Factorization Online. Available online: http:\/\/stringology.org\/papers\/PSC2013.pdf#page=115."},{"key":"ref_6","unstructured":"Chairungsee, S., and Crochemore, M. (October, January 28). Efficient Computing of Longest Previous Reverse Factors. Proceedings of the Computer Science and Information Technologies, Yerevan, Armenia."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-22321-1_1","article-title":"Hunting Redundancies in Strings","volume":"Volume 6795","author":"Badkobeh","year":"2011","journal-title":"International Conference on Developments in Language Theory"},{"key":"ref_8","unstructured":"Chairungsee, S. (2021, April 15). Searching for Gapped Palindrome. Available online: https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397509006409."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Charoenrak, S., and Chairungsee, S. (2017, January 27\u201329). Palindrome Detection Using On-Line Position. Proceedings of the 2017 International Conference on Information Technology, Singapore.","DOI":"10.1145\/3176653.3176661"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Charoenrak, S., and Chairungsee, S. (2019, January 20\u201323). Algorithm for Palindrome Detection by Suffix Heap. Proceedings of the 2019 7th International Conference on Information Technology: IoT and Smart City, Shanghai China.","DOI":"10.1145\/3377170.3377202"},{"key":"ref_11","first-page":"109","article-title":"Building the Minimal DFA for the Set of all Subwords of a Word On-line in Linear Time","volume":"Volume 172","author":"Blumer","year":"1984","journal-title":"International Colloquium on Automata, Languages, and Programming"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.jda.2010.12.001","article-title":"Position heaps: A simple and dynamic text indexing data structure","volume":"9","author":"Ehrenfeucht","year":"2011","journal-title":"J. Discret. Algorithms"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-642-38905-4_11","article-title":"New Algorithms for Position Heaps","volume":"Volume 7922","author":"Gagie","year":"2013","journal-title":"Annual Symposium on Combinatorial Pattern Matching"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.jda.2011.02.002","article-title":"Efficient algorithms for three variants of the LPF table","volume":"11","author":"Crochemore","year":"2012","journal-title":"J. Discret. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix Arrays: A New Method for On-Line String Searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_16","first-page":"205","article-title":"Longest Gapped Repeats and Palindromes","volume":"19","author":"Dumitran","year":"2017","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/j.ipl.2015.04.002","article-title":"Constructing LZ78 tries and position heaps in linear time for large alphabets","volume":"115","author":"Nakashima","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2048","DOI":"10.1007\/s00453-017-0333-1","article-title":"Lempel\u2013Ziv Factorization Powered by Space Efficient Suffix Trees","volume":"80","author":"Fischer","year":"2018","journal-title":"Algorithmica"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"K\u00f6ppl, D. (2021). Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees. Algorithms, 14.","DOI":"10.3390\/a14020044"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed Suffix Trees with Full Functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_24","first-page":"179","article-title":"Indexed Matching Statistics and Shortest Unique Substrings","volume":"Volume 8799","author":"Belazzougui","year":"2014","journal-title":"International Symposium on String Processing and Information Retrieval"},{"key":"ref_25","first-page":"593","article-title":"Computing Quasi Suffix Arrays","volume":"8","author":"Franek","year":"2003","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","article-title":"Computing Longest Previous Factor in linear time and applications","volume":"106","author":"Crochemore","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/3381417","article-title":"Linear-time String Indexing and Analysis in Small Space","volume":"16","author":"Belazzougui","year":"2020","journal-title":"ACM Trans. Algorithms"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Goto, K., and Bannai, H. (2014, January 26\u201328). Space Efficient Linear Time Lempel\u2013Ziv Factorization for Small Alphabets. Proceedings of the 2014 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2014.62"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-3-642-38527-8_14","article-title":"Lightweight Lempel\u2013Ziv Parsing","volume":"Volume 7933","author":"Kempa","year":"2013","journal-title":"International Symposium on Experimental Algorithms"},{"key":"ref_30","first-page":"432","article-title":"Faster Lightweight Lempel\u2013Ziv Parsing","volume":"Volume 9235","author":"Kosolobov","year":"2015","journal-title":"International Symposium on Mathematical Foundations of Computer Science"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., and Puglisi, S.J. (2016, January 10\u201312). Range Predecessor and Lempel\u2013Ziv Parsing. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA.","DOI":"10.1137\/1.9781611974331.ch143"},{"key":"ref_32","first-page":"696","article-title":"An Online Algorithm for Finding the Longest Previous Factors","volume":"Volume 5193","author":"Okanohara","year":"2008","journal-title":"European Symposium on Algorithms"},{"key":"ref_33","first-page":"339","article-title":"Faster Online Computation of the Succinct Longest Previous Factor Array","volume":"Volume 12098","author":"Prezza","year":"2020","journal-title":"Conference on Computability in Europe"},{"key":"ref_34","unstructured":"Bannai, H., Inenaga, S., and K\u00f6ppl, D. (, January 4\u20136July). Computing All Distinct Squares in Linear Time for Integer Alphabets. Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Warsaw, Poland. Available online: https:\/\/link.springer.com\/chapter\/10.1007\/978-3-662-48057-1_16."},{"key":"ref_35","unstructured":"Jacobson, G. (November, January 30). Space-efficient Static Trees and Graphs. Proceedings of the 30th Annual Symposium on Foundations of Computer Science Research, Triangle Park, NC, USA."},{"key":"ref_36","unstructured":"Clark, D.R. (1996). Compact Pat Trees. [Ph.D. Thesis, University of Waterloo]."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Baumann, T., and Hagerup, T. (2019, January 5\u20137). Rank-Select Indices Without Tears. Proceedings of the Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada. LNCS.","DOI":"10.1007\/978-3-030-24766-9_7"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Navarro, G., and Nekrich, Y. (2017, January 16\u201319). Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.26"},{"key":"ref_39","unstructured":"Burrows, M., and Wheeler, D.J. (1994). A Block Sorting Lossless Data Compression Algorithm, Digital Equipment Corporation. Technical Report 124."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the Complexity of Finite Sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","article-title":"Faster entropy-bounded compressed suffix trees","volume":"410","author":"Fischer","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1145\/321892.321896","article-title":"A New Linear-Time \u201cOn-Line\u201d Algorithm for Finding the Smallest Initial Palindrome of a String","volume":"22","author":"Manacher","year":"1975","journal-title":"J. ACM"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)00083-U","article-title":"Parallel Detection of all Palindromes in a String","volume":"141","author":"Apostolico","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_44","unstructured":"K\u00f6ppl, D. (2018). Exploring Regular Structures in Strings. [Ph.D. Thesis, TU Dortmund]."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_46","unstructured":"Fleischer, L., and Shallit, J.O. (2019). Words Avoiding Reversed Factors, Revisited. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/161\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:05:28Z","timestamp":1760162728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,21]]},"references-count":46,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060161"],"URL":"https:\/\/doi.org\/10.3390\/a14060161","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,21]]}}}