{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:54:47Z","timestamp":1676944487287},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"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":[[2008,7]]},"DOI":"10.1007\/s00453-007-9104-8","type":"journal-article","created":{"date-parts":[[2007,11,2]],"date-time":"2007-11-02T16:26:55Z","timestamp":1194020815000},"page":"298-314","source":"Crossref","is-referenced-by-count":10,"title":["Improved Approximate String Matching Using\u00a0Compressed Suffix Data Structures"],"prefix":"10.1007","volume":"51","author":[{"given":"Tak-Wah","family":"Lam","sequence":"first","affiliation":[]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[]},{"given":"Swee-Seong","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,1]]},"reference":[{"issue":"2","key":"9104_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":"9104_CR2","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0794\u2013803 (2000)"},{"key":"9104_CR3","unstructured":"Baeza-Yates, R.A., Navarro, G.: A practical index for text retrieval allowing errors. In: CLEI, pp.\u00a0273\u2013282 (1997)"},{"key":"9104_CR4","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.R.: Range searching over tree cross products. In: Proceedings of the 8th Annual European Symposium on Algorithms, pp.\u00a0120\u2013131 (2000)","DOI":"10.1007\/3-540-45253-2_12"},{"key":"9104_CR5","doi-asserted-by":"crossref","unstructured":"Cobbs, A.L.: Fast approximate matching using suffix trees. In: Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a041\u201354, July 1995","DOI":"10.1007\/3-540-60044-2_33"},{"key":"9104_CR6","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 the 36th Annual ACM Symposium on Theory of Computing, pp.\u00a091\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"9104_CR7","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 the 32nd ACM Symposium on Theory of Computing, pp.\u00a0397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"key":"9104_CR8","unstructured":"Hon, W.K., Sadakane, K., Sung, W.K.: Breaking a time-and-space barrier in constructing full-text indices. In: Proceedings of IEEE Symposium on Foundations of Computer Science, pp.\u00a0251\u2013260 (2003)"},{"key":"9104_CR9","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of Symposium on Foundations of Computer Science, pp.\u00a0549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"9104_CR10","doi-asserted-by":"crossref","unstructured":"Jokinen, P., Ukkonen, E.: Two algorithms for approximate string matching in static texts. In: Proceedings of the 16th International Symposium on Mathematical Foundations of Computer Science, pp.\u00a0240\u2013248, September 1991","DOI":"10.1007\/3-540-54345-7_67"},{"issue":"2","key":"9104_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms 10(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"issue":"3","key":"9104_CR12","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"9104_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1151","volume":"39","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39, 205\u2013222 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"9104_CR14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"key":"9104_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G., Baeza-Yates, R.: A new indexing method for approximate string matching. In: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a0163\u2013185 (1999)","DOI":"10.1007\/3-540-48452-3_13"},{"issue":"1","key":"9104_CR16","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 1(1), 205\u2013239 (2000)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"9104_CR17","first-page":"19","volume":"24","author":"G. Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Data Eng. Bull. 24(4), 19\u201327 (2001)","journal-title":"IEEE Data Eng. Bull."},{"key":"9104_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G., Sutinen, E., Tanninen, J., Tarhio, J.: Indexing text with approximate q-grams. In: Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a0350\u2013365 (2000)","DOI":"10.1007\/3-540-45123-4_29"},{"key":"9104_CR19","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0233\u2013242 (2002)"},{"key":"9104_CR20","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, 307\u2013311 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9104_CR21","doi-asserted-by":"crossref","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. (accepted)","DOI":"10.1007\/s00224-006-1198-x"},{"key":"9104_CR22","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P.H. Sellers","year":"1980","unstructured":"Sellers, P.H.: The theory and computation of evolutionary distances: pattern recognition. J. Algorithms 1, 359\u2013373 (1980)","journal-title":"J. Algorithms"},{"key":"9104_CR23","first-page":"257","volume-title":"Proceedings of the 3rd South American Workshop on String Processing","author":"F. Shi","year":"1996","unstructured":"Shi, F.: Fast approximate string matching with q-blocks sequences. In: Proceedings of the 3rd South American Workshop on String Processing, pp.\u00a0257\u2013271. Carleton University Press, Carleton (1996)"},{"key":"9104_CR24","doi-asserted-by":"crossref","unstructured":"Sutinen, E., Tarhio, J.: Filtration with q-samples in approximate string matching. In: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a050\u201363 (1996)","DOI":"10.1007\/3-540-61258-0_4"},{"key":"9104_CR25","doi-asserted-by":"crossref","unstructured":"Trinh, H.N.D., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. In: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a0434\u2013444 (2004)","DOI":"10.1007\/978-3-540-27801-6_33"},{"key":"9104_CR26","doi-asserted-by":"crossref","unstructured":"Ukkonen, E.: Approximate string-matching over suffix trees. In: Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, pp.\u00a0228\u2013242 (1993)","DOI":"10.1007\/BFb0029808"},{"key":"9104_CR27","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 \u03b8(n). Inf. Process. Lett. 17, 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-007-9104-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9104-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9104-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9104-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,1]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9104"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9104-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,1]]}}}