{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:06:50Z","timestamp":1743066410241,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031721991"},{"type":"electronic","value":"9783031722004"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-72200-4_24","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"321-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Faster and\u00a0Simpler Online\/Sliding Rightmost Lempel-Ziv Factorizations"],"prefix":"10.1007","author":[{"given":"Wataru","family":"Sumiyoshi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2922-9434","authenticated-orcid":false,"given":"Takuya","family":"Mieno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, 8-11 November 1998, Palo Alto, pp. 534\u2013544. IEEE Computer Society (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743504","DOI":"10.1109\/SFCS.1998.743504"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2018.10.033","volume":"792","author":"M Alzamel","year":"2019","unstructured":"Alzamel, M., Iliopoulos, C.S., Smyth, W.F., Sung, W.: Off-line and on-line algorithms for closed string factorization. Theor. Comput. Sci. 792, 12\u201319 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A Amir","year":"1995","unstructured":"Amir, A., Farach, M., Idury, R.M., Poutr\u00e9, J.A.L., Sch\u00e4ffer, A.A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258\u2013282 (1995)","journal-title":"Inf. Comput."},{"issue":"5","key":"24_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0020-0190(01)00275-7","volume":"82","author":"A Amir","year":"2002","unstructured":"Amir, A., Landau, G.M., Ukkonen, E.: Online timestamped text indexing. Inf. Process. Lett. 82(5), 253\u2013259 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00275-7","journal-title":"Inf. Process. Lett."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Badkobeh, G., et al.: Closed factorization. Discret. Appl. Math. 212, 23\u201329 (2016)","DOI":"10.1016\/j.dam.2016.04.009"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Puglisi, S.J.: Range predecessor and Lempel-Ziv parsing. In: SODA 2016, pp. 2053\u20132071 (2016)","DOI":"10.1137\/1.9781611974331.ch143"},{"issue":"12","key":"24_CR7","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1109\/TCOM.1986.1096485","volume":"34","author":"TC Bell","year":"1986","unstructured":"Bell, T.C.: Better OPM\/L text compression. IEEE Trans. Commun. 34(12), 1176\u20131182 (1986)","journal-title":"IEEE Trans. Commun."},{"key":"24_CR8","unstructured":"Bille, P., Cording, P.H., Fischer, J., G\u00f8rtz, I.L.: Lempel-Ziv compression in a sliding window. In: CPM 2017. LIPIcs, vol.\u00a078, pp. 15:1\u201315:11 (2017)"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-22300-6_25","volume-title":"Algorithms and Data Structures","author":"GS Brodal","year":"2011","unstructured":"Brodal, G.S., Davoodi, P., Srinivasa Rao, S.: Path minima queries in dynamic weighted trees. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 290\u2013301. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22300-6_25"},{"issue":"2","key":"24_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1240233.1240244","volume":"3","author":"H Chan","year":"2007","unstructured":"Chan, H., Hon, W., Lam, T.W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Trans. Algorithms 3(2), 21 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"24_CR11","doi-asserted-by":"publisher","unstructured":"Ellert, J., Fischer, J., Pedersen, M.R.: New advances in\u00a0rightmost Lempel-Ziv. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) SPIRE 2023. LNCS, vol. 14240, pp. 188\u2013202. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_15","DOI":"10.1007\/978-3-031-43980-3_15"},{"issue":"4","key":"24_CR12","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.1137\/120869511","volume":"42","author":"P Ferragina","year":"2013","unstructured":"Ferragina, P., Nitto, I., Venturini, R.: On the bit-complexity of Lempel-Ziv compression. SIAM J. Comput. 42(4), 1521\u20131541 (2013)","journal-title":"SIAM J. Comput."},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Fici, G.: A classification of Trapezoidal words. In: WORDS 2011. EPTCS, vol.\u00a063, pp. 129\u2013137 (2011)","DOI":"10.4204\/EPTCS.63.18"},{"key":"24_CR14","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. arXiv preprint arXiv:1302.3347 (2013)"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. In: CPM 2015, pp. 160\u2013171 (2015)","DOI":"10.1007\/978-3-319-19929-0_14"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Saks, M.E.: The cell probe complexity of dynamic data structures. In: STOC 1989, pp. 345\u2013354. ACM (1989)","DOI":"10.1145\/73007.73040"},{"issue":"2","key":"24_CR17","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0255(82)90058-5","volume":"27","author":"RH G\u00fcting","year":"1982","unstructured":"G\u00fcting, R.H., Wood, D.: The parenthesis tree. Inf. Sci. 27(2), 151\u2013162 (1982)","journal-title":"Inf. Sci."},{"issue":"4","key":"24_CR18","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: FOCS 1999, pp. 596\u2013604 (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Kreft, S., Navarro, G.: LZ77-like compression with fast random access. In: DCC 2010, pp. 239\u2013248 (2010)","DOI":"10.1109\/DCC.2010.29"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Larsson, N.J.: Extended application of suffix trees to data compression. In: DCC 1996, pp. 190\u2013199 (1996)","DOI":"10.1109\/DCC.1996.488324"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-319-07566-2_26","volume-title":"Combinatorial Pattern Matching","author":"NJ Larsson","year":"2014","unstructured":"Larsson, N.J.: Most recent match queries in on-line suffix trees. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 252\u2013261. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_26"},{"issue":"1","key":"24_CR23","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory 22(1), 75\u201381 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"24_CR24","unstructured":"Leonard, L., Inenaga, S., Bannai, H., Mieno, T.: Constant-time edge label and leaf pointer maintenance on sliding suffix trees (2024)"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing, 2nd edn. Cambridge University Press (2023). http:\/\/www.genome-scale.info\/","DOI":"10.1017\/9781009341257"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1\u201316:39 (2014)","DOI":"10.1145\/2601073"},{"key":"24_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1007\/978-3-540-87744-8_58","volume-title":"Algorithms - ESA 2008","author":"D Okanohara","year":"2008","unstructured":"Okanohara, D., Sadakane, K.: An online algorithm for finding the longest previous factors. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 696\u2013707. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87744-8_58"},{"key":"24_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-030-51466-2_31","volume-title":"Beyond the Horizon of Computability","author":"N Prezza","year":"2020","unstructured":"Prezza, N., Rosone, G.: Faster online computation of the succinct longest previous factor array. In: Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (eds.) CiE 2020. LNCS, vol. 12098, pp. 339\u2013352. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51466-2_31"},{"key":"24_CR29","unstructured":"Senft, M.: Suffix tree for a sliding window: an overview. In: WDS 2005, vol.\u00a05, pp. 41\u201346 (2005)"},{"issue":"4","key":"24_CR30","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982)","journal-title":"J. ACM"},{"issue":"3","key":"24_CR31","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"24_CR32","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"3","key":"24_CR33","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"DE Willard","year":"2000","unstructured":"Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030\u20131049 (2000). https:\/\/doi.org\/10.1137\/S0097539797322425","journal-title":"SIAM J. Comput."},{"issue":"3","key":"24_CR34","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:03:28Z","timestamp":1726686208000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}