{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T20:54:47Z","timestamp":1776113687152,"version":"3.50.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031721991","type":"print"},{"value":"9783031722004","type":"electronic"}],"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_7","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"88-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Revisiting the\u00a0Folklore Algorithm for\u00a0Random Access to Grammar-Compressed Strings"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6567-5346","authenticated-orcid":false,"given":"Alan M.","family":"Cleary","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4592-3891","authenticated-orcid":false,"given":"Joseph","family":"Winjum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8043-3919","authenticated-orcid":false,"given":"Jordan","family":"Dood","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":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-662-48350-3_13","volume-title":"Algorithms - ESA 2015","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Cording, P.H., Puglisi, S.J., Tabei, Y.: Access, rank, and select in grammar-compressed strings. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 142\u2013154. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_13"},{"issue":"2","key":"7_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/s00453-015-0068-9","volume":"77","author":"P Bille","year":"2017","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L.: Compressed subsequence matching and packed tree coloring. Algorithmica 77(2), 336\u2013348 (2017)","journal-title":"Algorithmica"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.jcss.2017.01.002","volume":"86","author":"P Bille","year":"2017","unstructured":"Bille, P., G\u00f8rtz, I.L., Cording, P.H., Sach, B., Vildh\u00f8j, H.W., Vind, S.: Fingerprints in compressed strings. J. Comput. Syst. Sci. 86, 171\u2013180 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"7_CR4","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)","journal-title":"SIAM J. Comput."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Blackman, D., Vigna, S.: Scrambled linear pseudorandom number generators. ACM Trans. Math. Softw. 47(4) (2021)","DOI":"10.1145\/3460772"},{"key":"7_CR6","unstructured":"Clark, D.: Compact pat trees (1997)"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Cleary, A., Dood, J.: Constructing the CDAWG CFG using LCP-intervals. In: 2023 Data Compression Conference (DCC), pp. 178\u2013187 (2023)","DOI":"10.1109\/DCC55655.2023.00026"},{"key":"7_CR8","unstructured":"The Computational Pan-Genomics Consortium: Computational pan-genomics: status, promises and challenges. Briefings Bioinform. 19(1), 118\u2013135 (2016)"},{"issue":"4","key":"7_CR9","doi-asserted-by":"publisher","first-page":"103","DOI":"10.3390\/a13040103","volume":"13","author":"I Furuya","year":"2020","unstructured":"Furuya, I., Takagi, T., Nakashima, Y., Inenaga, S., Bannai, H., Kida, T.: Practical grammar compression based on maximal repeats. Algorithms 13(4), 103 (2020)","journal-title":"Algorithms"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 240\u2013251. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28332-1_21"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Gagie, T., Goga, A., Jez, A., Navarro, G.: Space-efficient conversions from slps. In: LATIN 2024. LNCS, vol. 14578, pp. 146\u2013161 (2024). https:\/\/doi.org\/10.1007\/978-3-031-55598-5_10","DOI":"10.1007\/978-3-031-55598-5_10"},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-030-59212-7_16","volume-title":"String Processing and Information Retrieval","author":"T Gagie","year":"2020","unstructured":"Gagie, T., et al.: Practical random access to\u00a0SLP-compressed texts. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. LNCS, vol. 12303, pp. 221\u2013231. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_16"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-030-32686-9_3","volume-title":"String Processing and Information Retrieval","author":"T Gagie","year":"2019","unstructured":"Gagie, T., I, T., Manzini, G., Navarro, G., Sakamoto, H., Takabatake, Y.: Rpair: rescaling RePair with Rsync. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 35\u201344. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_3"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 27:1\u201327:40 (2021)","DOI":"10.1145\/3457389"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: Plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) Experimental Algorithms, pp. 326\u2013337. Springer International Publishing, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_28"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-27660-6_25","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K Goto","year":"2012","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Computing q-gram non-overlapping frequencies on SLP compressed texts. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 301\u2013312. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27660-6_25"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.jda.2012.07.006","volume":"18","author":"K Goto","year":"2013","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Fast q-gram mining on SLP compressed strings. J. Discrete Algorithms 18, 89\u201399 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Hufford, M.B., et al.: De novo assembly, annotation, and comparative analysis of 26 diverse maize genomes. Science 373(6555), 655\u2013662 (2021)","DOI":"10.1126\/science.abg5289"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ic.2014.09.009","volume":"240","author":"I Tomohiro","year":"2015","unstructured":"Tomohiro, I., et al.: Detecting regularities on grammar-compressed strings. Inf. Comput. 240, 74\u201389 (2015)","journal-title":"Inf. Comput."},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2015.01.019","volume":"578","author":"I Tomohiro","year":"2015","unstructured":"Tomohiro, I., Nishimoto, T., Inenaga, S., Bannai, H., Takeda, M.: Compressed automata for dictionary matching. Theor. Comput. Sci. 578, 30\u201341 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"7_CR21","first-page":"172","volume":"4","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nord. J. Comput. 4(2), 172\u2013186 (1997)","journal-title":"Nord. J. Comput."},{"issue":"11","key":"7_CR22","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"N Larsson","year":"2000","unstructured":"Larsson, N., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE 88(11), 1722\u20131732 (2000)","journal-title":"Proc. IEEE"},{"key":"7_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: a tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 228\u2013240. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_24"},{"issue":"2","key":"7_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on slp-compressed strings: a survey. Groups - Complexity - Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups - Complexity - Cryptol."},{"key":"7_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-319-02432-5_25","volume-title":"String Processing and Information Retrieval","author":"S Maruyama","year":"2013","unstructured":"Maruyama, S., Tabei, Y., Sakamoto, H., Sadakane, K.: Fully-online grammar compression. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 218\u2013229. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-02432-5_25"},{"issue":"8\u201310","key":"7_CR26","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8\u201310), 900\u2013913 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"7_CR27","first-page":"187","volume":"1","author":"M Miyazaki","year":"2000","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight line programs. J. Dis. Algorithms 1(1), 187\u2013204 (2000)","journal-title":"J. Dis. Algorithms"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part ii: compressed indexes. ACM Comput. Surv. 54(2) (2021)","DOI":"10.1145\/3432999"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Nunes, D.S.N., Louza, F., Gog, S., Ayala-Rinc\u00c3\u00b3n, M., Navarro, G.: A grammar compression algorithm based on induced suffix sorting. In: 2018 Data Compression Conference, pp. 42\u201351 (2018)","DOI":"10.1109\/DCC.2018.00012"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: ALENEX 2007, pp. 60\u201370","DOI":"10.1137\/1.9781611972870.6"},{"key":"7_CR31","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-38905-4_23","volume-title":"Combinatorial Pattern Matching","author":"Y Tabei","year":"2013","unstructured":"Tabei, Y., Takabatake, Y., Sakamoto, H.: A succinct grammar compression. In: Fischer, J., Sanders, P. (eds.) Combinatorial Pattern Matching, pp. 235\u2013246. Springer, Berlin Heidelberg, Berlin, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_23"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"Tanaka, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Computing convolution on grammar-compressed text. In: DCC 2013, pp. 451\u2013460. IEEE (2013)","DOI":"10.1109\/DCC.2013.53"},{"key":"7_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-38905-4_24","volume-title":"Combinatorial Pattern Matching","author":"E Verbin","year":"2013","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 247\u2013258. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_24"},{"key":"7_CR34","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-68552-4_12","volume-title":"WEA 2008","author":"S Vigna","year":"2008","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: McGeoch, C.C. (ed.) WEA 2008, pp. 154\u2013168. Springer, Berlin Heidelberg, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-68552-4_12"},{"key":"7_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-21458-5_27","volume-title":"Combinatorial Pattern Matching","author":"T Yamamoto","year":"2011","unstructured":"Yamamoto, T., Bannai, H., Inenaga, S., Takeda, M.: Faster subsequence and don\u2019t-care pattern matching on compressed texts. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 309\u2013322. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_27"},{"issue":"6","key":"7_CR36","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1038\/ng.3847","volume":"49","author":"JX Yue","year":"2017","unstructured":"Yue, J.X., et al.: Contrasting evolutionary genome dynamics between domesticated and wild yeasts. Nat. Genet. 49(6), 913\u2013924 (2017)","journal-title":"Nat. Genet."}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:02:19Z","timestamp":1726686139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"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"}}]}}