{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T17:40:06Z","timestamp":1770486006156,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,1,29]],"date-time":"2014-01-29T00:00:00Z","timestamp":1390953600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,7]]},"DOI":"10.1007\/s00453-014-9873-9","type":"journal-article","created":{"date-parts":[[2014,1,28]],"date-time":"2014-01-28T17:26:27Z","timestamp":1390929987000},"page":"791-817","source":"Crossref","is-referenced-by-count":6,"title":["Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error"],"prefix":"10.1007","volume":"72","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,1,29]]},"reference":[{"issue":"2","key":"9873_CR1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1006\/jagm.2000.1104","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms 37(2), 309\u2013325 (2000)","journal-title":"J. Algorithms"},{"key":"9873_CR2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/978-3-642-02441-2_14","volume-title":"Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D.: Faster and space-optimal edit distance \u201c1\u201d dictionary. In: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 154\u2013167 (2009)"},{"key":"9873_CR3","first-page":"748","volume-title":"Proceedings of the 19th Annual European Symposium on Algorithms (ESA)","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 748\u2013759 (2011)"},{"key":"9873_CR4","first-page":"427","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA)","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pp. 427\u2013438 (2010)"},{"key":"9873_CR5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-3-642-31265-6_24","volume-title":"Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"P. Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Sach, B., Vildh\u00f8j, H.W.: Time-space trade-offs for longest common extensions. In: Proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 293\u2013305 (2012)"},{"key":"9873_CR6","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-61258-0_6","volume-title":"Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"G.S. Brodal","year":"1996","unstructured":"Brodal, G.S., G\u0105sieniec, L.: Approximate dictionary queries. In: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 65\u201374 (1996)"},{"key":"9873_CR7","first-page":"120","volume-title":"Proceedings of the 8th Annual European Symposium on Algorithms (ESA)","author":"A.L. Buchsbaum","year":"2000","unstructured":"Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.: Range searching over tree cross products. In: Proceedings of the 8th Annual European Symposium on Algorithms (ESA), pp. 120\u2013131 (2000)"},{"issue":"2","key":"9873_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-008-9263-2","volume":"58","author":"H.-L. Chan","year":"2010","unstructured":"Chan, H.-L., Lam, T.W., Sung, W.-K., Tam, S.-L., Wong, S.-S.: Compressed indexes for approximate string matching. Algorithmica 58(2), 263\u2013281 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"9873_CR9","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.jda.2011.04.004","volume":"9","author":"H.-L. Chan","year":"2011","unstructured":"Chan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S.: A linear size index for approximate pattern matching. J. Discrete Algorithms 9(4), 358\u2013364 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"9873_CR10","first-page":"383","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D.R. Clark","year":"1996","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 383\u2013391 (1996)"},{"key":"9873_CR11","first-page":"91","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing (STOC)","author":"R. Cole","year":"2004","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 91\u2013100 (2004)"},{"key":"9873_CR12","volume-title":"Jewels of Stringology: Text Algorithms","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology: Text Algorithms. World Scientific, Singapore (2003)"},{"issue":"2","key":"9873_CR13","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P. Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"9873_CR14","unstructured":"Fano, R.M.: On the number of bits required to implement an associative memory. Memorandum\u00a061, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., n.d. (1971)"},{"issue":"4","key":"9873_CR15","doi-asserted-by":"crossref","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":"9873_CR16","first-page":"158","volume-title":"Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN)","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN), pp. 158\u2013169 (2010)"},{"issue":"9","key":"9873_CR17","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960)","journal-title":"Commun. ACM"},{"issue":"2","key":"9873_CR18","doi-asserted-by":"crossref","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."},{"key":"9873_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"9873_CR20","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"9873_CR21","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS)","author":"G. Jacobson","year":"1989","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554 (1989)"},{"issue":"2","key":"9873_CR22","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. 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."},{"key":"9873_CR23","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading (1973)"},{"key":"9873_CR24","first-page":"339","volume-title":"Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC)","author":"T.W. Lam","year":"2005","unstructured":"Lam, T.W., Sung, W.-K., Wong, S.-S.: Improved approximate string matching using compressed suffix data structures. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pp. 339\u2013348 (2005)"},{"issue":"3","key":"9873_CR25","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00453-007-9104-8","volume":"51","author":"T.W. Lam","year":"2008","unstructured":"Lam, T.W., Sung, W.-K., Wong, S.-S.: Improved approximate string matching using compressed suffix data structures. Algorithmica 51(3), 298\u2013314 (2008)","journal-title":"Algorithmica"},{"key":"9873_CR26","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/11496656_3","volume-title":"Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"M.G. Maa\u00df","year":"2005","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. In: Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 21\u201332 (2005)"},{"issue":"5","key":"9873_CR27","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9873_CR28","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. 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":"9873_CR29","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 37\u201342 (1996)"},{"key":"9873_CR30","first-page":"657","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Muthukrishnan","year":"2002","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 657\u2013666 (2002)"},{"key":"9873_CR31","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"6","key":"9873_CR32","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/S0020-0190(01)00298-8","volume":"82","author":"S.S. Rao","year":"2002","unstructured":"Rao, S.S.: Time-space trade-offs for compressed suffix arrays. Inf. Process. Lett. 82(6), 307\u2013311 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9873_CR33","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"9873_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"Proceedings of the 14th Annual Symposium on Switching and Automata Theory (FOCS)","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Annual Symposium on Switching and Automata Theory (FOCS), pp. 1\u201311 (1973)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9873-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9873-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9873-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9873-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,29]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["9873"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9873-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,29]]}}}