{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T19:10:06Z","timestamp":1751224206937,"version":"3.41.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,1,11]],"date-time":"2018-01-11T00:00:00Z","timestamp":1515628800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008617","name":"H\u00f8jteknologifonden","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008617","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["1323-00178"],"award-info":[{"award-number":["1323-00178"]}],"id":[{"id":"10.13039\/501100004836","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":[[2018,11]]},"DOI":"10.1007\/s00224-017-9839-9","type":"journal-article","created":{"date-parts":[[2018,1,11]],"date-time":"2018-01-11T05:25:54Z","timestamp":1515648354000},"page":"1715-1735","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Finger Search in Grammar-Compressed Strings"],"prefix":"10.1007","volume":"62","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6454-3555","authenticated-orcid":false,"given":"Anders Roy","family":"Christiansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,11]]},"reference":[{"key":"9839_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceeding of the 39th FOCS, pp. 534\u2013543 (1998)","DOI":"10.7146\/brics.v5i16.21956"},{"key":"9839_CR2","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Lonardi, S.: Some theory and practice of greedy off-line textual substitution. In: Proceeding of the DCC, pp. 119\u2013128 (1998)","DOI":"10.1109\/DCC.1998.672138"},{"key":"9839_CR3","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Lonardi, S.: Compression of biological sequences by greedy off-line textual substitution. In: Proceeding of the DCC, pp. 143\u2013152 (2000)","DOI":"10.1109\/DCC.2000.838154"},{"issue":"11","key":"9839_CR4","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1109\/5.892709","volume":"88","author":"A Apostolico","year":"2000","unstructured":"Apostolico, A., Lonardi, S.: Off-line compression by greedy textual substitution. Proc. IEEE 88(11), 1733\u20131744 (2000)","journal-title":"Proc. IEEE"},{"key":"9839_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cording, P.H., Puglisi, S.J., Tabei, Y.: Access, rank, and select in grammar-compressed strings. In: Proceeding of the 23rd ESA (2015)","DOI":"10.1007\/978-3-662-48350-3_13"},{"key":"9839_CR6","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Gawrychowski, P., Karkkainen, J., Ordonez, A., Puglisi, S., Tabei, Y.: Queries on lz-bounded encodings. In: Proceeding of the DCC, pp. 83\u201392 (2015)","DOI":"10.1109\/DCC.2015.69"},{"issue":"3","key":"9839_CR7","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"JL Bentley","year":"1976","unstructured":"Bentley, J.L., Yao, A.C.-C.: An almost optimal algorithm for unbounded searching. Inform. Process. Lett. 5(3), 82\u201387 (1976)","journal-title":"Inform. Process. Lett."},{"key":"9839_CR8","doi-asserted-by":"publisher","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L.: Compressed subsequence matching and packed tree coloring. Algorithmica, 1\u201313 (2015). https:\/\/doi.org\/10.1007\/s00453-015-0068-9","DOI":"10.1007\/s00453-015-0068-9"},{"key":"9839_CR9","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.jcss.2017.01.002","volume":"86","author":"P Bille","year":"2013","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 (2013). Announced at WADS","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9839_CR10","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2014","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 (2014). Announced at SODA 2011","journal-title":"SIAM J. Comput."},{"key":"9839_CR11","unstructured":"Blelloch, G.E., Maggs, B.M., Woo, S.L.M.: Space-efficient finger search on degree-balanced search trees. In: Proceeding of the 14th SODA, pp. 374\u2013383 (2003)"},{"key":"9839_CR12","doi-asserted-by":"crossref","unstructured":"Brodal, G.S.: Finger search trees. In: Handbook of Data Structures and Applications. Chapman and Hall\/CRC (2004)","DOI":"10.1201\/9781420035179.ch11"},{"issue":"2","key":"9839_CR13","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/S0022-0000(03)00013-8","volume":"67","author":"GS Brodal","year":"2003","unstructured":"Brodal, G.S., Lagogiannis, G., Makris, C., Tsakalidis, A.K., Tsichlas, K.: Optimal finger search trees in the pointer machine. J. Comput. Syst Sci. 67(2), 381\u2013418 (2003)","journal-title":"J. Comput. Syst Sci."},{"issue":"7","key":"9839_CR14","doi-asserted-by":"crossref","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). Announced at STOC 2002 and SODA 2002","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9839_CR15","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","volume":"111","author":"F Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fund. Inform. 111(3), 313\u2013337 (2011)","journal-title":"Fund. Inform."},{"key":"9839_CR16","doi-asserted-by":"crossref","unstructured":"Cording, P.H., Gawrychowski, P., Weimann, O.: Bookmarks in grammar-compressed strings. In: Proceeding of the 23rd SPIRE, pp. x\u2013y (2016)","DOI":"10.1007\/978-3-319-46049-9_15"},{"issue":"3","key":"9839_CR17","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(94)00115-4","volume":"52","author":"PF Dietz","year":"1994","unstructured":"Dietz, P.F., Raman, R.: A constant update time finger search tree. Inf. Process. Lett. 52(3), 147\u2013154 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9839_CR18","doi-asserted-by":"crossref","unstructured":"Farach, M., Muthukrishnan, S.: Perfect hashing for strings: formalization and algorithms. In: Proceeding of the 7th CPM, pp. 130\u2013140. Springer (1996)","DOI":"10.1007\/3-540-61258-0_11"},{"issue":"2","key":"9839_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0129054196000117","volume":"7","author":"R Fleischer","year":"1996","unstructured":"Fleischer, R.: A simple balanced search tree with o(1) worst-case update time. Int. J. Found. Comput. Sci. 7(2), 137\u2013150 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"9839_CR20","first-page":"23","volume":"12","author":"P Gage","year":"1994","unstructured":"Gage, P.: A new algorithm for data compression. The C Users J. 12(2), 23\u201338 (1994)","journal-title":"The C Users J."},{"key":"9839_CR21","doi-asserted-by":"crossref","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Proceeding of the 6th LATA, pp. 240\u2013251 (2012)","DOI":"10.1007\/978-3-642-28332-1_21"},{"key":"9839_CR22","doi-asserted-by":"crossref","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Proceeding of the 11th LATIN, pp. 731\u2013742. Springer (2014)","DOI":"10.1007\/978-3-642-54423-1_63"},{"key":"9839_CR23","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.jda.2014.10.003","volume":"32","author":"T Gagie","year":"2015","unstructured":"Gagie, T., Gawrychowski, P., Puglisi, S.J.: Approximate pattern matching in lz77-compressed texts. J. Discrete Algorithms 32, 64\u201368 (2015)","journal-title":"J. Discrete Algorithms"},{"key":"9839_CR24","unstructured":"Gagie, T., Hoobin, C., Puglisi, S.J.: Block graphs in practice. In: Proceeding of the ICABD, pp. 30\u201336 (2014)"},{"key":"9839_CR25","unstructured":"Ga\u0327sieniec, L., Kolpakov, R., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: Proceeding of the 15th DCC, p. 458 (2005)"},{"key":"9839_CR26","doi-asserted-by":"crossref","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding. In: Proceeding of the 26th CPM, pp. 219\u2013230. Springer (2015)","DOI":"10.1007\/978-3-319-19929-0_19"},{"key":"9839_CR27","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A new representation for linear lists. In: Proceeding of the 9Th STOC, pp. 49\u201360 (1977)","DOI":"10.1145\/800105.803395"},{"key":"9839_CR28","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.ic.2014.09.009","volume":"240","author":"T I","year":"2015","unstructured":"I, T., Matsubara, W., Shimohira, K., Inenaga, S., Bannai, H., Takeda, M., Narisawa, K., Shinohara, A.: Detecting regularities on grammar-compressed strings. Inform. Comput. 240, 74\u201389 (2015)","journal-title":"Inform. Comput."},{"issue":"2","key":"9839_CR29","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"9839_CR30","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.H.: Grammar based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"9839_CR31","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1109\/18.850665","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.H., Nelson, G.J., Cosman, P.: Universal lossless compression via multilevel pattern matching. IEEE Trans. Inf. Theory 46(5), 1227\u20131245 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9839_CR32","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Localized search in sorted lists. In: Proceeding of the 13th STOC, pp. 62\u201369, New York (1981)","DOI":"10.1145\/800076.802458"},{"issue":"11","key":"9839_CR33","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"NJ Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE 88(11), 1722\u20131732 (2000)","journal-title":"Proc. IEEE"},{"key":"9839_CR34","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: A new data structure for representing sorted lists. In: Proceeding of the WG, pp. 90\u2013112 (1981)","DOI":"10.1007\/3-540-10291-4_8"},{"key":"9839_CR35","doi-asserted-by":"crossref","unstructured":"Navarro, G., Ord\u00f3nez, A.: Grammar compressed sequences with rank\/select support. In: 21St SPIRE, pp. 31\u201344. Springer (2014)","DOI":"10.1007\/978-3-319-11918-2_4"},{"key":"9839_CR36","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"CG Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artif. Intell. Res. 7, 67\u201382 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"9839_CR37","unstructured":"Nishimoto, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Fully dynamic data structure for LCE queries in compressed space. In: Proceeding of the 41st MFCS, pp. 72:1\u201372:15 (2016)"},{"issue":"6","key":"9839_CR38","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: A probabilistic alternative to balanced trees. Commun. ACM 33(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"issue":"1-3","key":"9839_CR39","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"4\/5","key":"9839_CR40","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R Seidel","year":"1996","unstructured":"Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16(4\/5), 464\u2013497 (1996)","journal-title":"Algorithmica"},{"key":"9839_CR41","unstructured":"Shibata, Y., Kida, T., Fukamachi, S., Takeda, M., Shinohara, A., Shinohara, T., Arikawa, S.: Byte pair encoding: a text compression scheme that accelerates pattern matching. Technical Report DOI-TR-161, Dept. of Informatics Kyushu University (1999)"},{"issue":"3","key":"9839_CR42","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"key":"9839_CR43","doi-asserted-by":"crossref","unstructured":"Tanaka, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Computing convolution on grammar-compressed text. In: Proceeding of the 23rd DCC, pp. 451\u2013460 (2013)","DOI":"10.1109\/DCC.2013.53"},{"key":"9839_CR44","doi-asserted-by":"crossref","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":"1","key":"9839_CR45","first-page":"99","volume":"10","author":"P Emde Boas van","year":"1976","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Theory Comput. Syst. 10(1), 99\u2013127 (1976)","journal-title":"Theory Comput. Syst."},{"key":"9839_CR46","doi-asserted-by":"crossref","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Proceeding of the 24th CPM, pp. 247\u2013258 (2013)","DOI":"10.1007\/978-3-642-38905-4_24"},{"issue":"6","key":"9839_CR47","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"TA Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high-performance data compression. IEEE Computer 17(6), 8\u201319 (1984)","journal-title":"IEEE Computer"},{"issue":"3","key":"9839_CR48","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/18.841161","volume":"46","author":"EH Yang","year":"2000","unstructured":"Yang, E.H., Kieffer, J.C.: Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform \u2013 part one: without context models. IEEE Trans. Inf. Theory 46(3), 755\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9839_CR49","doi-asserted-by":"crossref","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"},{"issue":"5","key":"9839_CR50","doi-asserted-by":"crossref","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. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9839-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9839-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9839-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T18:34:43Z","timestamp":1751222083000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9839-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,11]]},"references-count":50,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9839"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9839-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,1,11]]}}}