{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:05:48Z","timestamp":1770480348528,"version":"3.49.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":26,"publisher":"Springer-Verlag","isbn-type":[{"value":"354056764X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029808","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T09:36:08Z","timestamp":1133429768000},"page":"228-242","source":"Crossref","is-referenced-by-count":69,"title":["Approximate string-matching over suffix trees"],"prefix":"10.1007","author":[{"given":"Esko","family":"Ukkonen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S. Altschul","year":"1990","unstructured":"Altschul, S., Gish, W., Miller, W., Myers, E. & Lipman, D. (1990): A basic local alignment search tool. J. of Molecular Biology 215, 403\u2013410.","journal-title":"J. of Molecular Biology"},{"key":"17_CR2","unstructured":"Baeza-Yates, R. A. & Gonnet, G. H.: All-against-all sequence matching (Extended Abstract)."},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A. Blumer","year":"1985","unstructured":"Blumer,A., Blumer,J., Haussler, D., Ehrenfeucht, A., Chen, M.T. and Seiferas, J. (1985): The smallest automaton recognizing the subwords of a text. Theor. Comp. Sci. 40, 31\u201355.","journal-title":"Theor. Comp. Sci."},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Chang, W. & Lampe, J. (1992): Theoretical and empirical comparisons of approximate string matching algorithms. Proc. Combinatorial Pattern Matching 1992, (Tucson, April 1992), Lect. Notes in Computer Science 644 (Springer-Verlag 1992), pp. 175\u2013184.","DOI":"10.1007\/3-540-56024-6_14"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Chang, W. & Lawler, E (1990): Approximate string matching in sublinear expected time. Proc. IEEE 1990 Ann. Symp. on Foundations of Computer Science, pp. 116\u2013124.","DOI":"10.1109\/FSCS.1990.89530"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M. (1986): Transducers and repetitions. Theor. Comp. Sci. 45, 63\u201386.","journal-title":"Theor. Comp. Sci."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Crochemore, M. (1988): String matching with constraints. Proc. MFCS'88 Symposium. Lect. Notes in Computer Science 324 (Springer-Verlag 1988), pp. 44\u201358.","DOI":"10.1007\/BFb0017130"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/356827.356830","volume":"12","author":"G. R. Dowling","year":"1980","unstructured":"Dowling, G. R. & Hall, P. (1980): Approximate string matching. ACM Comput. Surv. 12, 381\u2013402.","journal-title":"ACM Comput. Surv."},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Galil, Z. & Giancarlo, R. (1988): Data structures and algorithms for approximate string matching. J. Complexity 4, 33\u201372.","journal-title":"J. Complexity"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z. Galil","year":"1989","unstructured":"Galil, Z. & Park, K. (1989): An improved algorithm for approximate string matching. SIAM J. on Computing 19, 989\u2013999.","journal-title":"SIAM J. on Computing"},{"key":"17_CR11","volume-title":"A tutorial introduction to Computational Biochemistry using Darwin","author":"G. H. Gonnet","year":"1992","unstructured":"Gonnet, G. H. (1992): A tutorial introduction to Computational Biochemistry using Darwin. Informatik E. T. H. Zuerich, Switzerland."},{"key":"17_CR12","unstructured":"Gonnet, G.H., Baeza-Yates,R.A. & Snider, T. (1991): Lexicographical indices for text: Inverted files vs. PAT trees. Report OED-91-01, UW Centre for the New Oxford English Dictionary and Text Research, 1991."},{"key":"17_CR13","unstructured":"Jokinen, P. & Ukkonen, E. (1991): Two-algorithms for approximate string matching in static texts. Proc. MFCS'91, Lect. Notes in Computer Science 520 (Springer-Verlag 1991), pp. 240\u2013248."},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"G. Landau","year":"1988","unstructured":"Landau, G. & Vishkin, U. (1988): Fast string matching with k differences. J. Comp. Syst. Sci. 37, 63\u201378.","journal-title":"J. Comp. Syst. Sci."},{"key":"17_CR15","unstructured":"Manber, U. & Myers, G. (1990): Suffix arrays: A new method for on-line string searches. In: SODA-90, pp. 319\u2013327."},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"McCreight, E. M. (1976): A space economical suffix tree construction algorithm. J. ACM 23, 262\u2013272.","journal-title":"J. ACM"},{"key":"17_CR17","unstructured":"Myers, E. W.: A sublinear algorithm for approximate keyword searching. TR 90-25, Department of Computer Science, The Univ. of Arizona, Tucson (to appear in Algorithmica)."},{"key":"17_CR18","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. (1980): The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms 1, 359\u2013373.","journal-title":"J. Algorithms"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Tarhio, J. & Ukkonen, E. (1990): Boyer-Moore approach to approximate string matching. 2nd Scand. Workshop on Algorithm Theory, Lect. Notes in Computer Science 447 (Springer-Verlag 1990), pp. 348\u2013359. Full version is to appear in SIAM J. Comput. 22.","DOI":"10.1007\/3-540-52846-6_103"},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E. (1985): Finding approximate patterns in strings. J. Algorithms 6, 132\u2013137.","journal-title":"J. Algorithms"},{"key":"17_CR21","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1992","unstructured":"Ukkonen, E. (1992): Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science 92, 191\u2013211.","journal-title":"Theoretical Computer Science"},{"key":"17_CR22","unstructured":"Ukkonen, E. (1992): Constructing suffix trees on-line in linear time. In: J. van Leeuwen (ed.), Algorithms, Software, Architecture. Information Processing 92, vol. I, pp. 484\u2013492. Elsevier."},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Ukkonen, E. & Wood, D.: Approximate string matching with suffix automata. Algorithmica (to appear in 1993).","DOI":"10.1007\/BF01769703"},{"key":"17_CR24","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"Wagner, R. A. & Fischer, M. J. (1974): The string-to-string correction problem. J. ACM 21, 168\u2013173.","journal-title":"J. ACM"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973): Linear pattern matching algorithms. Proc. 14th IEEE Symp. Switching and Automata Theory, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"17_CR26","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"Wu, S. & Manber, U. (1992): Fast text searching allowing errors. Comm. ACM 35, 83\u201391.","journal-title":"Comm. ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029808","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:34:09Z","timestamp":1586594049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354056764X"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0029808","relation":{},"subject":[]}}