{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:36Z","timestamp":1740108336008,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:00:00Z","timestamp":1724371200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:00:00Z","timestamp":1724371200000},"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":["JP23K18466"],"award-info":[{"award-number":["JP23K18466"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00236-024-00465-9","type":"journal-article","created":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:15:25Z","timestamp":1724458525000},"page":"445-468","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear-size suffix tries and linear-size CDAWGs simplified and improved"],"prefix":"10.1007","volume":"61","author":[{"given":"Shunsuke","family":"Inenaga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,23]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cunial, F.: Fast label extraction in the CDAWG. In: Proceedings of the 24th International Symposium on String Processing and Information Retrieval, pp. 161\u2013175 (2017)","key":"465_CR1","DOI":"10.1007\/978-3-319-67428-5_14"},{"doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: LATIN 2000, vol. 1776, pp. 88\u201394 (2000)","key":"465_CR2","DOI":"10.1007\/10719839_9"},{"issue":"1","key":"465_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5\u201312 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"465_CR4","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. Syst. Sci. 48(2), 214\u2013230 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"465_CR5","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., Seiferas, J.: The smallest automation recognizing the subwords of a text. Theor. Comput. Sci. 40, 31\u201355 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"465_CR6","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"issue":"7","key":"465_CR7","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"465_CR8","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. SIAM J. Comput. 34(4), 894\u2013923 (2005)","journal-title":"SIAM J. Comput."},{"key":"465_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.tcs.2016.04.002","volume":"638","author":"M Crochemore","year":"2016","unstructured":"Crochemore, M., Epifanio, C., Grossi, R., Mignosi, F.: Linear-size suffix tries. Theor. Comput. Sci. 638, 171\u2013178 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"465_CR10","doi-asserted-by":"publisher","first-page":"114093","DOI":"10.1016\/j.tcs.2023.114093","volume":"973","author":"Y Fujishige","year":"2023","unstructured":"Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M.: Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets. Theor. Comput. Sci. 973, 114093 (2023)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Gasieniec, L., Kolpakov, R.M., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: DCC 2005, pp. 458 (2005)","key":"465_CR11"},{"unstructured":"Hendrian, D., Takagi, T., Inenaga, S.: Online Algorithms for Constructing Linear-size Suffix Trie. In: CPM 2019, pp. 30:1\u201330:19 (2019)","key":"465_CR12"},{"doi-asserted-by":"crossref","unstructured":"Hendrian, D., Takagi, T., Inenaga, S., Goto, K., Funakoshi, M.: Linear time online algorithms for constructing linear-size suffix trie. CoRR (2023). arXiv:2301.04295","key":"465_CR13","DOI":"10.1016\/j.tcs.2024.114765"},{"issue":"2","key":"465_CR14","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.dam.2004.04.012","volume":"146","author":"S Inenaga","year":"2005","unstructured":"Inenaga, S., Hoshino, H., Shinohara, A., Takeda, M., Arikawa, S., Mauri, G., Pavesi, G.: On-line construction of compact directed acyclic word graphs. Discret. Appl. Math. 146(2), 156\u2013179 (2005)","journal-title":"Discret. Appl. Math."},{"unstructured":"K\u00e4rkk\u00e4inen, J.: Personal communication (2017). StringMasters 2017 in Tokyo","key":"465_CR15"},{"doi-asserted-by":"crossref","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: STOC, pp. 827\u2013840 (2018)","key":"465_CR16","DOI":"10.1145\/3188745.3188814"},{"issue":"2","key":"465_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00453-016-0178-z","volume":"79","author":"K Narisawa","year":"2017","unstructured":"Narisawa, K., Hiratsuka, H., Inenaga, S., Bannai, H., Takeda, M.: Efficient computation of substring equivalence classes with suffix arrays. Algorithmica 79(2), 291\u2013318 (2017)","journal-title":"Algorithmica"},{"issue":"2","key":"465_CR18","first-page":"29:1","volume":"54","author":"G Navarro","year":"2022","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv. 54(2), 29:1-29:31 (2022)","journal-title":"ACM Comput. Surv."},{"key":"465_CR19","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.jda.2011.01.001","volume":"11","author":"J Radoszewski","year":"2012","unstructured":"Radoszewski, J., Rytter, W.: On the structure of compacted subword graphs of Thue\u2013Morse words and their applications. J. Discret. Algorithms 11, 15\u201324 (2012)","journal-title":"J. Discret. Algorithms"},{"issue":"1\u20133","key":"465_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel\u2013Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"465_CR21","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)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Takagi, T., Goto, K., Fujishige, Y., Inenaga, S., Arimura, H.: Linear-size CDAWG: new repetition-aware indexing and grammar compression. In: SPIRE 2017, pp. 304\u2013316 (2017)","key":"465_CR22","DOI":"10.1007\/978-3-319-67428-5_26"},{"issue":"2","key":"465_CR23","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0304-3975(02)00184-6","volume":"292","author":"M Takeda","year":"2003","unstructured":"Takeda, M., Fukuda, T., Nanri, I., Yamasaki, M., Tamari, K.: Discovering instances of poetic allusion from anthologies of classical Japanese poems. Theor. Comput. Sci. 292(2), 497\u2013524 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"465_CR24","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"},{"doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311. IEEE (1973)","key":"465_CR25","DOI":"10.1109\/SWAT.1973.13"},{"issue":"3","key":"465_CR26","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":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00465-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-024-00465-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00465-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T11:03:32Z","timestamp":1730718212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-024-00465-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,23]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["465"],"URL":"https:\/\/doi.org\/10.1007\/s00236-024-00465-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2024,8,23]]},"assertion":[{"value":"9 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2024","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 conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}