{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:42:01Z","timestamp":1770482521260,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,12,17]],"date-time":"2008-12-17T00:00:00Z","timestamp":1229472000000},"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":[[2010,10]]},"DOI":"10.1007\/s00453-008-9263-2","type":"journal-article","created":{"date-parts":[[2008,12,16]],"date-time":"2008-12-16T11:03:19Z","timestamp":1229425399000},"page":"263-281","source":"Crossref","is-referenced-by-count":19,"title":["Compressed Indexes for\u00a0Approximate String Matching"],"prefix":"10.1007","volume":"58","author":[{"given":"Ho-Leung","family":"Chan","sequence":"first","affiliation":[]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[]},{"given":"Siu-Lung","family":"Tam","sequence":"additional","affiliation":[]},{"given":"Swee-Seong","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,12,17]]},"reference":[{"key":"9263_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Indexing and dictionary matching with one error. In: Proceedings of Workshop on Algorithms and Data Structures, pp.\u00a0181\u2013192 (1999)","DOI":"10.1007\/3-540-48447-7_19"},{"key":"9263_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Landau, G., Lewenstein, M., Sokol, D.: Dynamic pattern, static text matching. In: Proceedings of Workshop on Algorithms and Data Structures, pp.\u00a0340\u2013352 (2003)","DOI":"10.1007\/978-3-540-45078-8_30"},{"key":"9263_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of Theoretical Informatics, 4th Latin American Symposium, pp.\u00a088\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"key":"9263_CR4","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.R.: Range searching over tree cross products. In: Proceedings of European Symposium on Algorithms, pp.\u00a0120\u2013131 (2000)","DOI":"10.1007\/3-540-45253-2_12"},{"key":"9263_CR5","doi-asserted-by":"crossref","unstructured":"Chan, H.L., Lam, T.W., Sung, W.K., Tam, S.L., Wong, S.S.: A linear-size index for approximate pattern matching. In: Proceedings of Combinatorial Pattern Matching, pp. 49\u201359 (2006)","DOI":"10.1007\/11780441_6"},{"key":"9263_CR6","doi-asserted-by":"crossref","unstructured":"Chavez, E., Navarro, G.: A metric index for approximate string matching. In: Proceedings of Latin American Theoretical Informatics, pp.\u00a0181\u2013195 (2002)","DOI":"10.1007\/3-540-45995-2_20"},{"key":"9263_CR7","doi-asserted-by":"crossref","unstructured":"Cobbs, A.: Fast approximate matching using suffix trees. In: Proceedings of Symposium on Combinatorial Pattern Matching, pp.\u00a041\u201354 (1995)","DOI":"10.1007\/3-540-60044-2_33"},{"key":"9263_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of Symposium on Theory of Computing, pp.\u00a091\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"9263_CR9","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of Symposium on Foundations of Computer Science, pp.\u00a0390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"9263_CR10","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proceedings of Symposium on Theory of Computing, pp.\u00a0397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"issue":"2","key":"9263_CR11","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.\u00a0Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9263_CR12","doi-asserted-by":"crossref","unstructured":"Huynh, T.N.D., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. In: Proceedings of Symposium on Combinatorial Pattern Matching, pp.\u00a0434\u2013444 (2004)","DOI":"10.1007\/978-3-540-27801-6_33"},{"key":"9263_CR13","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, 298\u2013314 (2008)","journal-title":"Algorithmica"},{"key":"9263_CR14","doi-asserted-by":"crossref","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. Technical Report TUM-10503, Fakult\u00e4t f\u00fcr Informatik, TU M\u00fcnchen (Mar. 2005)","DOI":"10.1007\/11496656_3"},{"issue":"5","key":"9263_CR15","doi-asserted-by":"crossref","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.\u00a0Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"2","key":"9263_CR16","first-page":"262","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J.\u00a0ACM 23(2), 262\u2013272 (1976)","journal-title":"J.\u00a0ACM"},{"key":"9263_CR17","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Proceedings of Conference on Foundations of Software Technology and Computer Science, pp.\u00a037\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"9263_CR18","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. J.\u00a0Comput. 31(3), 762\u2013776","DOI":"10.1137\/S0097539799364092"},{"key":"9263_CR19","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of 13th Symposium on Discrete Algorithms, pp.\u00a0657\u2013666 (2002)"},{"issue":"1","key":"9263_CR20","first-page":"205","volume":"1","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. J.\u00a0Discrete Algorithms 1(1), 205\u2013209 (2000). Special issue on Matching Patterns","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9263_CR21","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0233\u2013242 (2002)"},{"key":"9263_CR22","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0225\u2013232 (2002)"},{"key":"9263_CR23","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of Symposium on Switching and Automata Theory, pp.\u00a01\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"9263_CR24","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(n). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9263-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9263-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9263-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:03Z","timestamp":1559123103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9263-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,17]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9263"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9263-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,17]]}}}