{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T02:51:46Z","timestamp":1768531906970,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":70,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642082306","type":"print"},{"value":"9783662076750","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/978-3-662-07675-0_8","type":"book-chapter","created":{"date-parts":[[2013,3,26]],"date-time":"2013-03-26T18:44:33Z","timestamp":1364323473000},"page":"361-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["String Editing and Longest Common Subsequences"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,26]]},"reference":[{"key":"8_CR1","first-page":"255","volume-title":"Algorithms for finding patterns in strings, Handbook of Theoretical Computer Science, J. van Leeuwen, Ed.","author":"A Aho","year":"1990","unstructured":"Aho, A. V. [ 1990 ], Algorithms for finding patterns in strings, Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., Elsevier, Amsterdam, 255\u2013300."},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321958.321970","volume":"23","author":"AV Aho","year":"1976","unstructured":"Aho, A. V., D. S. Hirschberg\nand J. D. Ullman [ 1976 ], Bounds on the complexity of the longest common subsequence problem, J. Assoc. Comput. Mach., 23, 1\u201312.","journal-title":"J. Assoc. Comput. Mach"},{"key":"8_CR3","volume-title":"The Design and Analysis of Computer Algorithms, Addison-Wesley","author":"AV Aho","year":"1974","unstructured":"Aho, A. V., J. E. Hopcroft\nand J. D. Ullman [ 1974 ], The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA."},{"key":"8_CR4","first-page":"497","volume-title":"Proc. 29th Annual Ieee Symposium on Foundations of Computer Science","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A. and J. Park [ 1988 ], Notes on searching in multidimensional monotone arrays, in Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, IEEE Computer Society, Washington, DC, 497\u2013512."},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0020-0190(86)90044-X","volume":"23","author":"A Apostolico","year":"1986","unstructured":"Apostolico, A. [ 1986 ], Improving the worst case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings, Information Processing Letters\n23, 63\u201369.","journal-title":"Information Processing Letters"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0020-0190(87)90167-0","volume":"25","author":"A Apostolico","year":"1987","unstructured":"Apostolico, A. [ 1987 ], Remark on HSU-DU New Algorithm for the LCS Problem. Information Processing Letters\n25, 235\u2013236.","journal-title":"Information Processing Letters"},{"key":"8_CR7","unstructured":"Apostolico, A., Ed. [1994], Algorithmica\n4\/5, Special Issue on String Algorithmics and Its Applications."},{"key":"8_CR8","first-page":"253","volume-title":"Efficient parallel algorithms for string editing and related problems, Siam Journal on Computing","author":"A Apostolico","year":"1988","unstructured":"Apostolico, A., M. J. Atallah, L. L. Larmore and S. Mcfaddin [1990], Efficient parallel algorithms for string editing and related problems, SIAM Journal on Computing\n19, 968\u2013988. Also: Proceedings of the 26th Allerton Conf. on Comm., Control and Comp., Monticello, IL, Sept. 1988, 253\u2013263."},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90132-Y","volume":"92","author":"A Apostolico","year":"1992","unstructured":"Apostolico, A., S. Browne\nand C. Guerra [ 1992 ], Fast linear space computations of longest common subsequences, Theoretical Computer Science, 92, 3\u201317.","journal-title":"Theoretical Computer Science"},{"key":"8_CR10","volume-title":"Combinatorial Algorithms on Words","year":"1985","unstructured":"Apostolico, A. and Z. Galil, Eds. [ 1985 ], Combinatorial Algorithms on Words, Springer-Verlag, Berlin."},{"key":"8_CR11","volume-title":"Il (1985)","author":"A Apostolico","year":"1985","unstructured":"Apostolico, A. and C. Guerra [ 1985 ], A fast linear space algorithm for computing longest common subsequences, Proceedings of the 23rd Allerton Conference, Monticello, IL (1985)."},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A Apostolico","year":"1987","unstructured":"Apostolico, A. and C. Guerra [ 1987 ], The longest common subsequence problem revisited, Algorithmica, 2, 315\u2013336.","journal-title":"Algorithmica"},{"key":"8_CR13","first-page":"487","volume":"194","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., E. A. Dinic, M. A. Kronrod, and I. A. Faradzev[1970]. On economical construction of the transitive closure of a directed graph, Dokl. Akad. Nauk SSSR\n194, 487\u2013488 (in Russian). English translation in Soviet Math. Dokl. 11:5, 1209\u20131210.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/BF01188710","volume":"9","author":"MJ Atallah","year":"1993","unstructured":"Atallah, M. J. [ 1993 ] A Faster Parallel Algorithm for a Matrix Searching Problem, Algorithmica, 9, 156\u2013167.","journal-title":"Algorithmica"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"JL Bentley","year":"1976","unstructured":"Bentley, J. L. and A. C-C. Yao [ 1976 ], An almost optimal algorithm for unbounded searching, Inform. Process. Letters\n5, 82\u201387.","journal-title":"Inform. Process. Letters"},{"key":"8_CR16","volume-title":"Nucleic Acids and Protein Sequence Analysis","year":"1987","unstructured":"Bishop, M. J. and C. J Rawlings, Eds. [ 1987 ], Nucleic Acids and Protein Sequence Analysis, IRL Press, Oxford."},{"key":"8_CR17","volume-title":"Introductory Combinatorics","author":"KP Bogart","year":"1983","unstructured":"Bogart, K. P. [ 1983 ], Introductory Combinatorics, Pitman, N.Y."},{"key":"8_CR18","first-page":"19","volume-title":"A representation of linear lists with movable fingers. Proceedings of the 10-th STOC","author":"MR Brown","year":"1978","unstructured":"Brown, M. R. and R. E. Tarjan [ 1978 ], A representation of linear lists with movable fingers. Proceedings of the 10-th STOC, San Diego, CA, 19\u201329."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Chang, W. I. and E. L. Lawler [1990], Approximate string matching in sublinear expected time, in Proc. 31st Annual IEEE Symp. on Foundations of Computer Science, St. Louis, MO, 116\u2013124","DOI":"10.1109\/FSCS.1990.89530"},{"key":"8_CR20","first-page":"807","volume-title":"Combinatorial Pattern Matching 1991, M. Crochemore and D. GUSFIELD, EDS., Proceedings of the 5th Annual Symposium, Asilomar, CA, June 1994, Springer-Verlag Lecture Notes in Computer Science Vol","author":"KM Chao","year":"1994","unstructured":"Chao, K. M. [1994], Computing all suboptimal alignments in linear space, in Combinatorial Pattern Matching\n1991, M. Crochemore\nand D. Gusfield, Eds., Proceedings of the 5th Annual Symposium, Asilomar, CA, June 1994, Springer-Verlag Lecture Notes in Computer Science Vol. 807 (1994)."},{"key":"8_CR21","volume-title":"N.y","author":"M Crochemore","year":"1994","unstructured":"Crochemore, M. and W. Rytter [ 1994 ], Text Algorithms, Oxford University Press, N.Y."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R Dilworth","year":"1950","unstructured":"Dilworth, R. P. [1950], A decomposition theorem for partially ordered sets, Ann. Math. 51, 161\u2013165.","journal-title":"Ann. Math"},{"key":"8_CR23","volume-title":"Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences","year":"1990","unstructured":"Doolittle, R. F., Ed. [ 1990 ], Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, Methods of Enzymology 183, Academic Press, San Diego, CA."},{"key":"8_CR24","unstructured":"van Emde Boas, P. [ 1975 ], Preserving order in a forest in less than logarithmic time, Proc. 16th FOCS, 75\u201384."},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D Eppstein","year":"1988","unstructured":"Eppstein, D. and Z. Galil [ 1988 ], Parallel algorithmic techniques for combinatorial computation, Ann. Rev. Comput. Sci., 3, 233\u2013283.","journal-title":"Ann. Rev. Comput. Sci"},{"key":"8_CR26","first-page":"513","volume-title":"Sparse dynamic programming, Proc. Symp. on Discrete Algorithms","author":"D Eppstein","year":"1990","unstructured":"Eppstein, D., Z. Galil, R. Giancarlo, and G. Italiano [ 1990 ]. Sparse dynamic programming, Proc. Symp. on Discrete Algorithms, San Francisco, CA, 513\u2013522."},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M. L. [ 1975 ], On Computing the Length of Longest Increasing Subsequences, Discrete Mathematics\n11, 29\u201335.","journal-title":"Discrete Mathematics"},{"key":"8_CR28","first-page":"693","volume":"20","author":"H Fuchs","year":"1977","unstructured":"Fuchs, H., Z. M. Kedem, and S. P. Uselton [ 1977 ], Optimal surface reconstruction from planar contours, Communications of the Assoc. Comput. Mach., 20, 693\u2013702.","journal-title":"Communications of the Assoc. Comput. Mach"},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z Galil","year":"1988","unstructured":"Galil Z. and R. Giancarlo [ 1988 ], Data structures and algorithms for approximate string matching, J. Complexity 4, 33\u201372.","journal-title":"J. Complexity"},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z Galil","year":"1990","unstructured":"Galil, Z. and K. Park [ 1990 ], An improved algorithm for approximate string matching, SIAM Jour. Computing 19, 989\u2013999.","journal-title":"Siam Jour. Computing"},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh, O. [ 1982 ]. An improved algorithm for matching biological sequences, J. Mol. Biol. 162, 705\u2013708.","journal-title":"J. Mol. Biol"},{"key":"8_CR32","volume-title":"Sequence Analysis in Molecular Biology","author":"G Heijne","year":"1987","unstructured":"von\nHeijne, G. [ 1987 ], Sequence Analysis in Molecular Biology, Academic Press, San Diego."},{"issue":"6","key":"8_CR33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg, D.S. [ 1975 ], A linear space algorithm for computing maximal common subsequences, CACM\n18, 6, 341\u2013343.","journal-title":"Cacm"},{"issue":"4","key":"8_CR34","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg, D. S. [ 1977 ], Algorithms for the longest common subsequence problem, JACM\n24, 4, 664\u2013675.","journal-title":"Jacm"},{"issue":"1","key":"8_CR35","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/0020-0190(78)90037-6","volume":"7","author":"DS Hirschberg","year":"1978","unstructured":"Hirschberg, D. S. [ 1978 ], An information theoretic lower bound for the longest common subsequence problem, Inform. Process. Lett. 7: 1, 40\u201341.","journal-title":"Inform. Process. Lett"},{"key":"8_CR36","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0022-0000(84)90025-4","volume":"29","author":"WJ Hsu","year":"1984","unstructured":"Hsu, W. J., and M. W.Du [ 1984 ], New algorithms for the LCS Problem, J. Comput. System Sci., 29, 133\u2013152.","journal-title":"J. Comput. System Sci"},{"issue":"5","key":"8_CR37","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J. W. and T. G. Szymanski [ 1977 ], A fast algorithm for computing longest common subsequences, CACM\n20, 5, 350\u2013353.","journal-title":"Cacm"},{"key":"8_CR38","volume-title":"An Introduction to Parallel Algorithms, Addison-Wesley","author":"J Jaa","year":"1992","unstructured":"Ja\nJa, J. [ 1992 ], An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA."},{"key":"8_CR39","first-page":"644","volume-title":"Springer-verlag","author":"G Jacobson","year":"1992","unstructured":"Jacobson, G. and K. P. Vo [1992], Heaviest increasing\/common subsequence problems, in Combinatorial Pattern Matching, Proceedings of the Third Annual Symposium, A. Apostolico, M. Crochemore, Z. Galil and U. Manger, Eds., Tucson, Arizona, 1992. Springer-Verlag, Berlin, Lecture Notes in Computer Science 644, 52\u201366."},{"key":"8_CR40","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"DB Johnson","year":"1982","unstructured":"Johnson, D. B. [ 1982 ]. A priority queue in which initialization and queue operations take O(log log D) time, Math. Systems Theory 15, 295\u2013309.","journal-title":"Math. Systems Theory"},{"key":"8_CR41","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1070\/IM1985v024n03ABEH001245","volume":"24","author":"AG Ivanov","year":"1985","unstructured":"Ivanov, A. G. [ 1985 ], Recognition of an approximate occurrence of. words on a Turing machine in real time, Math. USSR Izv., 24, 479\u2013522.","journal-title":"Math. Ussr Izv"},{"key":"8_CR42","first-page":"677","volume-title":"Proc. 18th Allerton Conference on Communication","author":"ZM Kedem","year":"1980","unstructured":"Kedem, Z. M. and H. Fuchs [1980], On finding several shortest paths in certain graphs, in Proc. 18th Allerton Conference on Communication, Control, and Computing, October 1980, pp. 677\u2013683."},{"key":"8_CR43","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF00265993","volume":"24","author":"SK Kumar","year":"1987","unstructured":"Kumar, S. K. and C. P. Rangan [ 1987 ], A linear space algorithm for the LCS problem, Acta Informatica\n24, 353\u2013362.","journal-title":"Acta Informatica"},{"key":"8_CR44","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"RE Ladner","year":"1980","unstructured":"Ladner, R. E., and M. J. Fischer [ 1980 ], Parallel prefix computation, J. Assoc. Comput. Mach., 27, 831\u2013838.","journal-title":"J. Assoc. Comput. Mach"},{"key":"8_CR45","first-page":"220","volume-title":"Proc. 18th Annual Acm STOC, New York","author":"Landau","year":"1986","unstructured":"Landau. G. M. and U. Vishkin [ 1986 ], Introducing efficient parallelism into approximate string matching and a new serial algorithm, in Proc. 18th Annual ACM STOC, New York, 1986, 220\u2013230."},{"key":"8_CR46","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"GM Landau","year":"1988","unstructured":"Landau, G. M. and U. Vishkin [ 1988 ], Fast string matching with k differences, Jour. Comp. and System Sci. 37, 63\u201378.","journal-title":"Jour. Comp. and System Sci"},{"key":"8_CR47","volume-title":"Introduction to Parallel Algorithms and Architectures, Morgan Kaufmann","author":"FT Leighton","year":"1992","unstructured":"Leighton, F. T. [ 1992 ], Introduction to Parallel Algorithms and Architectures, Morgan Kaufmann, San Mateo, CA."},{"key":"8_CR48","first-page":"10","volume-title":"Binary codes capable of correcting deletions, insertions and reversals","author":"V Levenshtein","year":"1966","unstructured":"Levenshtein, V. I. [ 1966 ], Binary codes capable of correcting deletions, insertions and reversals, Soviet Phys. Dokl., 10, 707\u2013710."},{"key":"8_CR49","first-page":"363","volume-title":"A systolic array for rapid string comparison Proc. Chapel Hill Conf. on Very Large Scale Integration, H. Fucs","author":"RJ Lipton","year":"1985","unstructured":"Lipton, R. J. and D. Lopresti [ 1985 ], A systolic array for rapid string comparison Proc. Chapel Hill Conf. on Very Large Scale Integration, H. Fucs, Ed., Computer Science Press, 363\u2013376."},{"key":"8_CR50","volume-title":"Mathematical and computational problems in the analysis of molecular sequences, Bull. Math. Bio","year":"1984","unstructured":"H. M. Martinez, Ed. [ 1984 ], Mathematical and computational problems in the analysis of molecular sequences, Bull. Math. Bio. 46, ( Special Issue Honoring M. O. Dayhoff )."},{"key":"8_CR51","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W. J. and M. S. Paterson [ 1980 ], A faster algorithm computing string edit distances, J. Comput. System Sci., 20, 18\u201331.","journal-title":"J. Comput. System Sci"},{"key":"8_CR52","first-page":"1988","volume-title":"A fast parallel algorithm to determine edit distance, Tech. Report CMU-CS-88-130, Department of Computer Science, Carnegie Mellon University","author":"T Mathies","year":"1988","unstructured":"Mathies, T. R. [ 1988 ], A fast parallel algorithm to determine edit distance, Tech. Report CMU-CS-88\u2013130, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, April 1988."},{"key":"8_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data structures and algorithms 1: sorting and searching","author":"K Mehlhorn","year":"1984","unstructured":"Mehlhorn, K. [ 1984 ], Data structures and algorithms 1: sorting and searching, EATCS Monographs on TCS, Springer-Verlag, Berlin."},{"key":"8_CR54","volume-title":"11-17","author":"EW Myers","year":"1988","unstructured":"Myers, E. W. and W. Miller [ 1988 ], Optimal alignments in linear space, Comp. Appl. Biosc. 4, 1, 11-17."},{"key":"8_CR55","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"EW Myers","year":"1986","unstructured":"Myers, E. W. [ 1986 ], An O(ND) difference algorithm and its variations, Algorithmica\n1, 251\u2013266.","journal-title":"Algorithmica"},{"key":"8_CR56","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N Nakatsu","year":"1982","unstructured":"Nakatsu, N., Y. Kambayashi, and S. Yajima [ 1982 ], A longest common subsequence algorithm suitable for similar text strings, Acta Informatica\n18, 171\u2013179.","journal-title":"Acta Informatica"},{"key":"8_CR57","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"RB Needleman","year":"1973","unstructured":"Needleman, R. B. and C. D. Wunsch [ 1973 ], A general method applicable to the search for similarities in the amino-acid sequence of two proteins, J. Molecular Bio., 48, 443\u2013453.","journal-title":"J. Molecular Bio"},{"key":"8_CR58","volume-title":"J. Parallel Distributed Comput","author":"S Ranka","year":"1988","unstructured":"Ranka, S. and S. Sahni [ 1988 ], String editing on an SIMD hypercube multi-computer, Tech. Report 88\u201329, Department of Computer Science, University of Minnesota, March 1988, J. Parallel Distributed Comput."},{"key":"8_CR59","volume-title":"Formal Languages","author":"A Salomaa","year":"1973","unstructured":"Salomaa, A. [ 1973 ] Formal Languages, Academic Press, Orlando, Fl."},{"key":"8_CR60","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D Sankoff","year":"1972","unstructured":"Sankoff, D.[ 1972 ], Matching sequences under deletion-insertion constraints, Proc. Nat. Acad. Sci. U.S.A., 69, 4\u20136.","journal-title":"Proc. Nat. Acad. Sci. U.S.A"},{"key":"8_CR61","volume-title":"String Edits and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983","unstructured":"Sankoff, D. and J. B. Kruskal, Eds. [ 1983 ], Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA."},{"key":"8_CR62","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0012-365X(73)80007-X","volume":"4","author":"D Sankoff","year":"1973","unstructured":"Sankoff, D. and P. H. Sellers [ 1973 ], Shortcuts, Diversions and Maximal Chains in Partially Ordered Sets, Discrete Mathematics, 4, 287\u2013293.","journal-title":"Discrete Mathematics"},{"key":"8_CR63","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"PH Sellers","year":"1980","unstructured":"Sellers, P. H. [ 1980 ], The theory and computation of evolutionary distance: pattern recognition, J. Algorithms, 1, 359\u2013373.","journal-title":"J. Algorithms"},{"key":"8_CR64","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith, T. F. and M. S. Waterman [ 1981 ], Identification of Common Molecular Subsequences, Journal of Molecular Biology\n147, 195\u2013197.","journal-title":"Journal of Molecular Biology"},{"key":"8_CR65","doi-asserted-by":"publisher","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":"8_CR66","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R. A. and M. J. Fischer [ 1974 ], The string to string correction problem, J. Assoc. Comput. Mach., 21, 168\u2013173.","journal-title":"J. Assoc. Comput. Mach"},{"key":"8_CR67","volume-title":"Mathematical Methods for Dna sequences","year":"1989","unstructured":"Waterman, M. S. (Ed.) [ 1989 ], Mathematical Methods for DNA sequences, CRC Press, Boca Raton."},{"key":"8_CR68","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/321921.321923","volume":"23","author":"CK Wong","year":"1976","unstructured":"Wong, C. K. and A. K. Chandra [ 1976 ], Bounds for the string editing problem, J. Assoc. Comput. Mach., 23, 13\u201316.","journal-title":"J. Assoc. Comput. Mach"},{"key":"8_CR69","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0020-0190(90)90035-V","volume":"35","author":"S Wu","year":"1990","unstructured":"Wu, S., U. Manber, E. W. Myers, and W. Miller [ 1990 ]. An O(NP) sequence comparison algorithm, Info. Proc. Letters\n35, 317\u2013323.","journal-title":"Info. Proc. Letters"},{"key":"8_CR70","volume-title":"And E","author":"S Wu","year":"1991","unstructured":"Wu, S., U. Manber, and E. Myers [ 1991 ]. Improving the running times for some string-matching problems."}],"container-title":["Handbook of Formal Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-07675-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T12:21:50Z","timestamp":1768220510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-07675-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783642082306","9783662076750"],"references-count":70,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-07675-0_8","relation":{},"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"26 March 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}