{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:45:38Z","timestamp":1770489938926,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,10,22]],"date-time":"2019-10-22T00:00:00Z","timestamp":1571702400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,22]],"date-time":"2019-10-22T00:00:00Z","timestamp":1571702400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-019-00637-x","type":"journal-article","created":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T04:30:17Z","timestamp":1571805017000},"page":"316-337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast Compressed Self-indexes with Deterministic Linear-Time Construction"],"prefix":"10.1007","volume":"82","author":[{"given":"J. Ian","family":"Munro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,22]]},"reference":[{"issue":"1","key":"637_CR1","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/s00453-012-9726-3","volume":"69","author":"J Barbay","year":"2014","unstructured":"Barbay, J., Claude, F., Gagie, T., Navarro, G., Nekrich, Y.: Efficient fully-compressed sequence representations. Algorithmica 69(1), 232\u2013268 (2014)","journal-title":"Algorithmica"},{"key":"637_CR2","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-15775-2_37","volume-title":"Algorithms \u2013 ESA 2010","author":"Djamal Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: Proceedings of 18th Annual European Symposium on Algorithms (ESA), LNCS 6346, pp. 427\u2013438 (2010)"},{"key":"637_CR3","first-page":"133","volume-title":"Lecture Notes in Computer Science","author":"Djamal Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional Burrows\u2013Wheeler transform. In: Proceedings of 21st Annual European Symposium on Algorithms (ESA), pp. 133\u2013144 (2013)"},{"key":"637_CR4","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Linear-time string indexing and analysis in small space. CoRR, \narXiv:1609.06378\n\n (2016)"},{"key":"637_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. ACM Trans. Algorithms 10(4), Article 23 (2014)","DOI":"10.1145\/2635816"},{"key":"637_CR6","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms 11(4), Article 31 (2015)","DOI":"10.1145\/2629339"},{"key":"637_CR7","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Deterministic indexing for packed strings. In: Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 78, Article 6 (2017)"},{"key":"637_CR8","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"637_CR9","unstructured":"Clark, D.R.: Compact PAT Trees. PhD thesis, University of Waterloo, Canada (1996)"},{"issue":"2","key":"637_CR10","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/s00453-013-9860-6","volume":"72","author":"R Cole","year":"2015","unstructured":"Cole, R., Kopelowitz, T., Lewenstein, M.: Suffix trays and suffix trists: structures for faster text indexing. Algorithmica 72(2), 450\u2013466 (2015)","journal-title":"Algorithmica"},{"key":"637_CR11","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 137\u2013143 (1997)"},{"issue":"4","key":"637_CR12","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"637_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms 3(2), Article 20 (2007)","DOI":"10.1145\/1240233.1240243"},{"issue":"1","key":"637_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"371","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 371(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"637_CR15","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-319-19929-0_14","volume-title":"Combinatorial Pattern Matching","author":"Johannes Fischer","year":"2015","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. In: Proceedings of 26th Annual Symposium on Combinatorial Pattern Matching (CPM), LNCS 9133, pp. 160\u2013171 (2015)"},{"issue":"2","key":"637_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"637_CR17","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.ipl.2006.04.008","volume":"99","author":"T Gagie","year":"2006","unstructured":"Gagie, T.: Large alphabets and incompressibility. Inf. Process. Lett. 99(6), 246\u2013251 (2006)","journal-title":"Inf. Process. Lett."},{"key":"637_CR18","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"637_CR19","unstructured":"Grossi, R., Orlandi, A., Raman, R., Rao, S.S.: More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In: Proceedings of 26th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 517\u2013528 (2009)"},{"issue":"2","key":"637_CR20","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"637_CR21","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.Bro, Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"issue":"6","key":"637_CR22","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2\u20134","key":"637_CR23","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2\u20134), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2\u20134","key":"637_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms 3(2\u20134), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"637_CR25","doi-asserted-by":"crossref","unstructured":"Lee, S., Park, K.: Dynamic rank-select structures with applications to run-length encoded texts. In: Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 95\u2013106 (2007)","DOI":"10.1007\/978-3-540-73437-6_12"},{"issue":"5","key":"637_CR26","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"637_CR27","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows\u2013Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"637_CR28","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"637_CR29","unstructured":"Munro, I., Navarro, G., Nekrich, Y.: Fast compressed self-indexes with deterministic linear-time construction. In: Proceedings of 28th Annual International Symposium on Algorithms and Computation (ISAAC), LIPIcs 92, Article 57 (2017)"},{"key":"637_CR30","first-page":"37","volume-title":"Lecture Notes in Computer Science","author":"J. Ian Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Proceedings of 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), LNCS 1180, pp. 37\u201342 (1996)"},{"key":"637_CR31","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Navarro, G., Nekrich, Y.: Space-efficient construction of compressed indexes in deterministic linear time. In: Proceedings of 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 408\u2013424 (2017)","DOI":"10.1137\/1.9781611974782.26"},{"key":"637_CR32","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2012.03.005","volume":"438","author":"JI Munro","year":"2012","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations and functions. Theor. Comput. Sci. 438, 74\u201388 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"637_CR33","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"Gonzalo Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys 39(1), Article 2 (2007)","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"637_CR34","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1137\/140998949","volume":"46","author":"G Navarro","year":"2017","unstructured":"Navarro, G., Nekrich, Y.: Time-optimal top-$$k$$ document retrieval. SIAM J. Comput. 46(1), 89\u2013113 (2017)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"637_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601073","volume":"10","author":"Gonzalo Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), Article 16 (2014)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"637_CR36","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294\u2013313 (2003)","journal-title":"J. Algorithms"},{"issue":"4","key":"637_CR37","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"637_CR38","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"637_CR39","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":"637_CR40","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of 14th Annual Symposium on Switching and Automata Theory (FOCS), pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00637-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00637-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00637-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T23:24:51Z","timestamp":1603236291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00637-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,22]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["637"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00637-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,22]]},"assertion":[{"value":"17 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}