{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:39:10Z","timestamp":1776764350815,"version":"3.51.2"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T00:00:00Z","timestamp":1765929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T00:00:00Z","timestamp":1765929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP23H04378"],"award-info":[{"award-number":["JP23H04378"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00224-025-10245-8","type":"journal-article","created":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:20:45Z","timestamp":1765959645000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["LZ78 Substring Compression in Compressed Space"],"prefix":"10.1007","volume":"70","author":[{"given":"Hiroki","family":"Shibata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,17]]},"reference":[{"key":"10245_CR1","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. In: Proceedings of the SODA, pp. 321\u2013330 (2005)"},{"key":"10245_CR2","doi-asserted-by":"publisher","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression (extended abstract). In: Proceedings of the STOC, pp. 30\u201339 (1978). https:\/\/doi.org\/10.1145\/800133.804329","DOI":"10.1145\/800133.804329"},{"key":"10245_CR3","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2013.10.010","volume":"525","author":"O Keller","year":"2014","unstructured":"Keller, O., Kopelowitz, T., Feibish, S.L., Lewenstein, M.: Generalized substring compression. Theor. Comput. Sci. 525, 42\u201354 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.10.010","journal-title":"Theor. Comput. Sci."},{"key":"10245_CR4","doi-asserted-by":"publisher","unstructured":"K\u00f6ppl, D.: Non-overlapping LZ77 factorization and LZ78 substring compression queries with suffix trees. Algorithms 14(2)(44), 1\u201321 (2021). https:\/\/doi.org\/10.3390\/a14020044","DOI":"10.3390\/a14020044"},{"key":"10245_CR5","doi-asserted-by":"publisher","unstructured":"K\u00f6ppl, D.: Computing LZ78-derivates with suffix trees. In: Bilgin, A., Fowler, J.E., Serra-Sagrist\u00e0, J., Ye, Y., Storer, J.A. (eds.) Data Compression Conference, DCC 2024, Snowbird, UT, USA, March 19-22, 2024, pp. 133\u2013142. IEEE, Snowbird, UT, USA (2024). https:\/\/doi.org\/10.1109\/DCC58796.2024.00021","DOI":"10.1109\/DCC58796.2024.00021"},{"key":"10245_CR6","doi-asserted-by":"publisher","unstructured":"Babenko, M.A., Gawrychowski, P., Kociumaka, T., Starikovskaya, T.: Wavelet trees meet suffix trees. In: Proceedings of the SODA, pp. 572\u2013591 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.39","DOI":"10.1137\/1.9781611973730.39"},{"key":"10245_CR7","unstructured":"Kociumaka, T.: Efficient data structures for internal queries in texts. PhD thesis, University of Warsaw (2018)"},{"key":"10245_CR8","doi-asserted-by":"publisher","unstructured":"Nakashima, Y., I, T., Inenaga, S., Bannai, H., Takeda, M.: Constructing LZ78 tries and position heaps in linear time for large alphabets. Inf. Process. Lett. 115(9), 655\u2013659 (2015) https:\/\/doi.org\/10.1016\/j.ipl.2015.04.002","DOI":"10.1016\/j.ipl.2015.04.002"},{"key":"10245_CR9","doi-asserted-by":"publisher","unstructured":"Fischer, J., I, T., K\u00f6ppl, D., Sadakane, K.: Lempel\u2013Ziv factorization powered by space efficient suffix trees. Algorithmica 80(7), 2048\u20132081 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0333-1","DOI":"10.1007\/s00453-017-0333-1"},{"key":"10245_CR10","doi-asserted-by":"crossref","unstructured":"K\u00f6ppl, D.: Substring compression variations and LZ78-derivates. CoRR arXiv:2409.14649 (2024)","DOI":"10.1016\/j.is.2025.102553"},{"key":"10245_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A Blumer","year":"1985","unstructured":"Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.I.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31\u201355 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90157-4","journal-title":"Theor. Comput. Sci."},{"key":"10245_CR12","doi-asserted-by":"publisher","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: LZD factorization: Simple and practical online grammar compression with variable-to-fixed encoding. In: Proceedings of the CPM. LNCS, vol. 9133, pp. 219\u2013230 (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_19","DOI":"10.1007\/978-3-319-19929-0_19"},{"key":"10245_CR13","doi-asserted-by":"crossref","unstructured":"Miller, V.S., Wegman, M.N.: Variations on a theme by Ziv and Lempel. In: Combinatorial Algorithms on Words, Berlin, Heidelberg, pp. 131\u2013140 (1985)","DOI":"10.1007\/978-3-642-82456-2_9"},{"issue":"1","key":"10245_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3426473","volume":"17","author":"AR Christiansen","year":"2021","unstructured":"Christiansen, A.R., Ettienne, M.B., Kociumaka, T., Navarro, G., Prezza, N.: Optimal-time dictionary-compressed indexes. ACM Trans. Algorithms 17(1), 8\u20131839 (2021). https:\/\/doi.org\/10.1145\/3426473","journal-title":"ACM Trans. Algorithms"},{"key":"10245_CR15","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Cunial, F.: Representing the suffix tree with the CDAWG. In: Proceedings of the CPM. LIPIcs, vol. 78, pp. 7\u20131713 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.7","DOI":"10.4230\/LIPIcs.CPM.2017.7"},{"key":"10245_CR16","doi-asserted-by":"publisher","unstructured":"Bannai, H., Gawrychowski, P., Inenaga, S., Takeda, M.: Converting SLP to LZ78 in almost linear time. In: Proceedings of the CPM. LNCS, vol. 7922, pp. 38\u201349 (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_6","DOI":"10.1007\/978-3-642-38905-4_6"},{"key":"10245_CR17","doi-asserted-by":"publisher","unstructured":"Arimura, H., Inenaga, S., Kobayashi, Y., Nakashima, Y., Sue, M.: Optimally computing compressed indexing arrays based on the compact directed acyclic word graph. In: Proceedings of the SPIRE. LNCS, vol. 14240, pp. 28\u201334 (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_3","DOI":"10.1007\/978-3-031-43980-3_3"},{"key":"10245_CR18","doi-asserted-by":"publisher","unstructured":"Badkobeh, G., Gagie, T., Inenaga, S., Kociumaka, T., Kosolobov, D., Puglisi, S.J.: On two LZ78-style grammars: Compression bounds and compressed-space computation. In: Proceedings of the SPIRE. LNCS, vol. 10508, pp. 51\u201367 (2017). https:\/\/doi.org\/10.1007\/978-3-319-67428-5_5","DOI":"10.1007\/978-3-319-67428-5_5"},{"key":"10245_CR19","doi-asserted-by":"publisher","unstructured":"Shibata, H., K\u00f6ppl, D.: LZ78 substring compression with CDAWGs. In: Proceedings of the SPIRE. Lecture Notes in Computer Science, vol. 14899, pp. 289\u2013305. Springer, Puerto Vallarta, Mexico (2024). https:\/\/doi.org\/10.1007\/978-3-031-72200-4_22","DOI":"10.1007\/978-3-031-72200-4_22"},{"issue":"5","key":"10245_CR20","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory 24(5), 530\u2013536 (1978). https:\/\/doi.org\/10.1109\/TIT.1978.1055934","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10245_CR21","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the SWAT, pp. 1\u201311 (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"},{"issue":"5","key":"10245_CR22","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993). https:\/\/doi.org\/10.1137\/0222058","journal-title":"SIAM J. Comput."},{"key":"10245_CR23","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Grossi, R., Gupta, A., Shah, R., Vitter, J.S.: On searching compressed string collections cache-obliviously. In: Proceedings of the PODS, pp. 181\u2013190 (2008). https:\/\/doi.org\/10.1145\/1376916.1376943","DOI":"10.1145\/1376916.1376943"},{"key":"10245_CR24","doi-asserted-by":"publisher","unstructured":"Crochemore, M., V\u00e9rin, R.: Direct construction of compact directed acyclic word graphs. In: Proceedings of the CPM. LNCS, vol. 1264, pp. 116\u2013129 (1997). https:\/\/doi.org\/10.1007\/3-540-63220-4_55","DOI":"10.1007\/3-540-63220-4_55"},{"issue":"3","key":"10245_CR25","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(01)00152-1","volume":"80","author":"M Raffinot","year":"2001","unstructured":"Raffinot, M.: On maximal repeats in strings. Inf. Process. Lett. 80(3), 165\u2013169 (2001). https:\/\/doi.org\/10.1016\/S0020-0190(01)00152-1","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10245_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2006.07.025","volume":"363","author":"W Rytter","year":"2006","unstructured":"Rytter, W.: The structure of subword graphs and suffix trees of fibonacci words. Theor. Comput. Sci. 363(2), 211\u2013223 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.07.025","journal-title":"Theor. Comput. Sci."},{"key":"10245_CR27","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, Palo Alto, California (1994)"},{"key":"10245_CR28","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Proceedings of the CPM. LNCS, vol. 9133, pp. 26\u201339 (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_3","DOI":"10.1007\/978-3-319-19929-0_3"},{"issue":"1","key":"10245_CR29","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/3375890","volume":"67","author":"T Gagie","year":"2020","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in bwt-runs bounded space. J. ACM 67(1), 2\u20131254 (2020). https:\/\/doi.org\/10.1145\/3375890","journal-title":"J. ACM"},{"issue":"4","key":"10245_CR30","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1109\/TIT.2022.3224382","volume":"69","author":"T Kociumaka","year":"2023","unstructured":"Kociumaka, T., Navarro, G., Prezza, N.: Toward a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory 69(4), 2074\u20132092 (2023). https:\/\/doi.org\/10.1109\/TIT.2022.3224382","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10245_CR31","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In: Proceedings of the FOCS, pp. 1877\u20131886 (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00114","DOI":"10.1109\/FOCS57990.2023.00114"},{"issue":"3","key":"10245_CR32","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/S00778-003-0107-Z","volume":"12","author":"J Yang","year":"2003","unstructured":"Yang, J., Widom, J.: Incremental computation and maintenance of temporal aggregates. VLDB J. 12(3), 262\u2013283 (2003). https:\/\/doi.org\/10.1007\/S00778-003-0107-Z","journal-title":"VLDB J."},{"key":"10245_CR33","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Proceedings of the ESA. LNCS, vol. 8737, pp. 455\u2013466 (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_38","DOI":"10.1007\/978-3-662-44777-2_38"},{"key":"10245_CR34","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Kosolobov, D., Puglisi, S.J., Raman, R.: Weighted ancestors in suffix trees revisited. In: Proceedings of the CPM. LIPIcs, vol. 191, pp. 8\u20131815 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.8","DOI":"10.4230\/LIPIcs.CPM.2021.8"},{"issue":"1","key":"10245_CR35","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"10245_CR36","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015). https:\/\/doi.org\/10.1137\/130936889","journal-title":"SIAM J. Comput."},{"key":"10245_CR37","doi-asserted-by":"publisher","unstructured":"Ehrhardt, M., Mulzer, W.: Delta-fast tries: Local searches in bounded universes with linear space. In: Proceedings of the WADS, pp. 361\u2013372 (2017). https:\/\/doi.org\/10.1007\/978-3-319-62127-2_31","DOI":"10.1007\/978-3-319-62127-2_31"},{"key":"10245_CR38","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Predecessor search with distance-sensitive query time. arXiv:1209.5441 (2012)"},{"issue":"3","key":"10245_CR39","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985). https:\/\/doi.org\/10.1145\/3828.3835","journal-title":"J. ACM"},{"key":"10245_CR40","doi-asserted-by":"publisher","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. In: Proceedings of the SODA, pp. 1459\u20131477 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.96","DOI":"10.1137\/1.9781611975031.96"},{"issue":"2","key":"10245_CR41","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/3434399","volume":"54","author":"G Navarro","year":"2021","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part i: repetitiveness measures. ACM Comput. Surv. 54(2), 29\u201312931 (2021). https:\/\/doi.org\/10.1145\/3434399","journal-title":"ACM Comput. Surv."},{"key":"10245_CR42","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: From theory to practice. ACM Journal of Experimental Algorithmics 13, 1\u201312111231 (2008). https:\/\/doi.org\/10.1145\/1412228.1455268","DOI":"10.1145\/1412228.1455268"},{"key":"10245_CR43","unstructured":"Nishimoto, T., Tabei, Y.: Dynamic suffix array in optimal compressed space. arXiv:2404.07510 (2024)"},{"key":"10245_CR44","unstructured":"Nishimoto, T., Tabei, Y.: Dynamic r-index: An updatable self-index for highly repetitive strings. arXiv:2504.19482 (2025)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10245-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10245-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10245-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:20Z","timestamp":1776760940000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10245-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,17]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10245"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10245-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,17]]},"assertion":[{"value":"12 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"1"}}