{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:37Z","timestamp":1725470737502},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_21","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"208-219","source":"Crossref","is-referenced-by-count":2,"title":["Compressed Indexes for Approximate String Matching"],"prefix":"10.1007","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","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48447-7_19","volume-title":"Algorithms and Data Structures","author":"A. Amir","year":"1999","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Indexing and dictionary matching with one error. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 181\u2013192. Springer, Heidelberg (1999)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.R.: Range searching over tree cross products. In: European Symposium on Algorithms, pp. 120\u2013131 (2000)","DOI":"10.1007\/3-540-45253-2_12"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Chavez, E., Navarro, G.: A metric index for approximate string matching. In: Proceedings of Latin American Theoretical Informatics, pp. 181\u2013195 (2002)","DOI":"10.1007\/3-540-45995-2_20"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Cobbs, A.: Fast approximate matching using suffix trees. In: Proceedings of Symposium on Combinatorial Pattern Matching, pp. 41\u201354 (1995)","DOI":"10.1007\/3-540-60044-2_33"},{"key":"21_CR5","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. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11780441_6","volume-title":"Combinatorial Pattern Matching","author":"H.L. Chan","year":"2006","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: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 49\u201359. Springer, Heidelberg (2006)"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic Data Structures with Applications. In: Symposium on Foundations of Computer Science, pp. 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"21_CR8","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. 397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","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 Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-27801-6_33","volume-title":"Combinatorial Pattern Matching","author":"T.N.D. Huynh","year":"2004","unstructured":"Huynh, T.N.D., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 434\u2013444. Springer, Heidelberg (2004)"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Lam, T.W., Sung, W.K., Wong, S.S.: Improved approximate string matching using compressed suffix data structures. In: Proceedings of International Symposium on Algorithms and Computation (2005)","DOI":"10.1007\/11602613_35"},{"key":"21_CR12","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 (March 2005)","DOI":"10.1007\/11496656_3"},{"issue":"5","key":"21_CR13","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 Journal on Computing\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"21_CR14","doi-asserted-by":"publisher","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. Journal of the ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"Journal of the ACM"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Proceedings of Conference on Foundations of Software Technology and Computer Science, pp. 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"21_CR16","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of 13th Symposium on Discrete Algorithms, pp. 657\u2013666 (2002)"},{"issue":"1","key":"21_CR17","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. Discrete Algorithms\u00a01(1), 205\u2013209 (2000)","journal-title":"J. Discrete Algorithms"},{"key":"21_CR18","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. 233\u2013242 (2002)"},{"key":"21_CR19","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. 225\u2013232 (2002)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear Pattern Matching Algorithms. In: Proceedings of Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"21_CR21","doi-asserted-by":"publisher","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). Information Processing Letters\u00a017(2), 81\u201384 (1983)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:27Z","timestamp":1605642027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11841036_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}