{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:15:45Z","timestamp":1742390145405},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514657"},{"type":"electronic","value":"9783540481409"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51465-1_6","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:57:23Z","timestamp":1330185443000},"page":"79-92","source":"Crossref","is-referenced-by-count":4,"title":["Sequence comparison: Some theory and some practice"],"prefix":"10.1007","author":[{"given":"Imre","family":"Simon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"A. V. Aho","year":"1976","unstructured":"A. V. Aho, D. S. Hirschberg, and J. D. Ullman. Bounds on the complexity of the longest common subsequence problem. J. ACM 23:1\u201312, 1976.","journal-title":"J. ACM"},{"key":"6_CR2","volume-title":"Data Structures and Algorithms","author":"A. V. Aho","year":"1983","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley Pu. Co., Reading, MA, 1983."},{"key":"6_CR3","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Pu. Co., Reading, MA, 1974."},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(86)90091-8","volume":"23","author":"L. Allison","year":"1986","unstructured":"L. Allison and T. I. Dix. A bit string longest common subsequence algorithm. Inf. Process. Lett., 23:305\u2013310, 1986.","journal-title":"Inf. Process. Lett."},{"key":"6_CR5","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0020-0190(86)90044-X","volume":"23","author":"A. Apostolico","year":"1986","unstructured":"A. Apostolico. Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings. Inf. Process. Lett., 23:63\u201369, 1986.","journal-title":"Inf. Process. Lett."},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0020-0190(87)90167-0","volume":"25","author":"A. Apostolico","year":"1987","unstructured":"A. Apostolico. Remark on the Hsu-Du new algorithm for the longest common subsequence problem. Inf. Process. Lett., 25:235\u2013236, 1987.","journal-title":"Inf. Process. Lett."},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315\u2013336, 1987.","journal-title":"Algorithmica"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1090\/S0025-5718-1968-0228216-8","volume":"22","author":"R. M. Baer","year":"1968","unstructured":"R. M. Baer and P. Brock. Natural sorting over permutation spaces. Math. Comp., 22:385\u2013410, 1968.","journal-title":"Math. Comp."},{"key":"6_CR9","unstructured":"V. Chv\u00e1tal, D. A. Klarner, and D. E. Knuth. Selected combinatorial research problems. Technical Report STAN-CS-72-292, Computer Science Department, Stanford University, 1972."},{"key":"6_CR10","unstructured":"V. Chv\u00e1tal and D. Sankoff. Longest common subsequences of random sequences. Technical Report STAN-CS-75-477, Computer Science Department, Stanford University, 1975."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"306","DOI":"10.2307\/3212444","volume":"12","author":"V. Chv\u00e1tal","year":"1975","unstructured":"V. Chv\u00e1tal and D. Sankoff. Longest common subsequences of two random sequences. J. Appl. Prob., 12:306\u2013315, 1975.","journal-title":"J. Appl. Prob."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"M. Crochemore. Longest common factor of two words. In Proceedings of CAAP'87, Pisa, Italy, pages 26\u201336, 1987.","DOI":"10.1007\/3-540-17660-8_45"},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0012-365X(79)90057-8","volume":"26","author":"J. Deken","year":"1979","unstructured":"J. Deken. Some limit results for longest common subsequences. Discrete Math., 26:17\u201331, 1979.","journal-title":"Discrete Math."},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M. L. Fredman","year":"1975","unstructured":"M. L. Fredman. On computing the length of longest increasing subsequences. Discrete Math., 11:29\u201335, 1975.","journal-title":"Discrete Math."},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"J. Gallant, D. Maier, and J. A. Storer. On finding minimal length superstrings. J. Comput. Syst. Sci., 20:50\u201358, 1980.","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR16","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/356827.356830","volume":"12","author":"P. A. V. Hall","year":"1980","unstructured":"P. A. V. Hall and G. R. Dowling. Approximate string matching. ACM Comput. Surv., 12:381\u2013402, 1980.","journal-title":"ACM Comput. Surv."},{"key":"6_CR17","unstructured":"J. J. Hebrard. Distances sur les mots. Application \u00e0 la recherche de motifs. Th\u00e8se de 3e cycle, Universit\u00e9 de Haute-Normandie, 1984."},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/359460.359467","volume":"21","author":"P. Heckel","year":"1978","unstructured":"P. Heckel. A technique for isolating differences between files. Commun. ACM, 21:264\u2013268, 1978.","journal-title":"Commun. ACM"},{"key":"6_CR19","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D. S. Hirschberg","year":"1977","unstructured":"D. S. Hirschberg. Algorithms for the longest common subsequence problem. J. ACM, 24:664\u2013675, 1977.","journal-title":"J. ACM"},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/0020-0190(78)90037-6","volume":"7","author":"D. S. Hirschberg","year":"1978","unstructured":"D. S. Hirschberg. An information theoretic lower bound for the longest common subsequence problem. Inf. Process. Lett., 7:40\u201341, 1978.","journal-title":"Inf. Process. Lett."},{"key":"6_CR21","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D. S. Hirschberg","year":"1975","unstructured":"D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18:341\u2013343, 1975.","journal-title":"Commun. ACM"},{"key":"6_CR22","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01840351","volume":"2","author":"D. S. Hirschberg","year":"1987","unstructured":"D. S. Hirschberg and L. L. Larmore. The set lcs problem. Algorithmica, 2:91\u201395, 1987.","journal-title":"Algorithmica"},{"key":"6_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0022-0000(84)90025-4","volume":"29","author":"W. J. Hsu","year":"1984","unstructured":"W. J. Hsu and M. W. Du. New algorithms for the LCS problem. J. Comput. Syst. Sci., 29:133\u2013152, 1984.","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR24","unstructured":"J. W. Hunt and M. D. McIlroy. An algorithm for differential file comparison. Technical Report #41, Computing Science, Bell Laboratories, 1976."},{"key":"6_CR25","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J. W. Hunt","year":"1977","unstructured":"J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Commun. ACM, 20:350\u2013353, 1977.","journal-title":"Commun. ACM"},{"key":"6_CR26","volume-title":"The Art of Computer Programming, Vol. 3, Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley Pu. Co., Reading, MA, 1973."},{"key":"6_CR27","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R. Lowrance","year":"1975","unstructured":"R. Lowrance and R. A. Wagner. An extension of the string-to-string correction problem. J. ACM, 22:177\u2013183, 1975.","journal-title":"J. ACM"},{"key":"6_CR28","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1977","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. J. ACM, 25:322\u2013336, 1977.","journal-title":"J. ACM"},{"key":"6_CR29","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. J. Masek","year":"1980","unstructured":"W. J. Masek and M. S. Paterson. A faster algorithm computing string edit distances. J. Comput. Syst. Sci., 20:18\u201331, 1980.","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, 1984."},{"key":"6_CR31","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1002\/spe.4380151102","volume":"15","author":"W. Miller","year":"1985","unstructured":"W. Miller and E. W. Myers. A file comparison program. Software \u2014 Practice and Experience, 15:1025\u20131040, 1985.","journal-title":"Software \u2014 Practice and Experience"},{"key":"6_CR32","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0020-0255(80)90025-0","volume":"20","author":"A. Mukhopadhyay","year":"1980","unstructured":"A. Mukhopadhyay. A fast algorithm for the longest common subsequence problem. Information Sciences, 20:69\u201382, 1980.","journal-title":"Information Sciences"},{"key":"6_CR33","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N. Nakatsu","year":"1982","unstructured":"N. Nakatsu, Y. Kambayashi, and S. Yajima. A longest common subsequence algorithm suitable for similar text strings. Acta Inf., 18:171\u2013179, 1982.","journal-title":"Acta Inf."},{"key":"6_CR34","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S. B. Needleman","year":"1970","unstructured":"S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Molecular Biology, 48:443\u2013453, 1970.","journal-title":"J. Molecular Biology"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Y. Robert and M. Tchuente. A systolic array for the longest common subsequence problem. Inf. Process. Lett., 21:191\u2013198, 19885.","DOI":"10.1016\/0020-0190(85)90058-4"},{"key":"6_CR36","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"D. Sankoff. Matching sequences under deletion\/insertion constraints. Proc. Nat. Acad. Sci. U.S.A., 69:4\u20136, 1972.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"6_CR37","volume-title":"Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"D. Sankoff and J. B. Kruskal. Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Addison-Wesley Pu. Co., Reading, MA, 1983."},{"key":"6_CR38","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","volume":"6","author":"S. M. Selkow","year":"1977","unstructured":"S. M. Selkow. The tree to tree editing problem. Inf. Process. Lett., 6:184\u2013186, 1977.","journal-title":"Inf. Process. Lett."},{"key":"6_CR39","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0097-3165(74)90050-8","volume":"16","author":"P. H. Sellers","year":"1974","unstructured":"P. H. Sellers. An algorithm for the distance between two finite sequences. J. Comb. Th. A, 16:253\u2013258, 1974.","journal-title":"J. Comb. Th. A"},{"key":"6_CR40","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0126070","volume":"26","author":"P. H. Sellers","year":"1974","unstructured":"P. H. Sellers. On the theory and computation of evolutionary distances. SIAM J. Appl. Math., 26:787\u2013793, 1974.","journal-title":"SIAM J. Appl. Math."},{"key":"6_CR41","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. H. Sellers","year":"1980","unstructured":"P. H. Sellers. The theory and computation of evolutionary distances: pattern recognition. J. of Algorithms, 1:359\u2013373, 1980.","journal-title":"J. of Algorithms"},{"key":"6_CR42","unstructured":"T. G. Szymanski. A special case of the maximal common subsequence problem. Technical Report TR-170, Computer Science Lab., Princeton University, 1975."},{"key":"6_CR43","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/357401.357404","volume":"2","author":"W. F. Tichy","year":"1984","unstructured":"W. F. Tichy. The string-to-string correction problem with block moves. ACM Trans. Comput. Syst., 2:309\u2013321, 1984.","journal-title":"ACM Trans. Comput. Syst."},{"key":"6_CR44","doi-asserted-by":"crossref","unstructured":"S. M. Ulam. Some combinatorial problems studied experimentally on computing machines. In S. K. Zaremba, editor, Applications of Number Theory to Numerical Analysis, pages 1\u20133, Academic Press, apa, 1972.","DOI":"10.1016\/B978-0-12-775950-0.50007-8"},{"key":"6_CR45","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF00288928","volume":"4","author":"T. K. Vintsyuk","year":"1968","unstructured":"T. K. Vintsyuk. Speech discrimination by dynamic programming. Kibernetika, 4:81\u201388, 1968.","journal-title":"Kibernetika"},{"key":"6_CR46","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. ACM, 21:168\u2013173, 1974.","journal-title":"J. ACM"},{"key":"6_CR47","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/321921.321923","volume":"23","author":"C. K. Wong","year":"1976","unstructured":"C. K. Wong and A. K. Chandra. Bounds for the string editing problem. J. ACM, 23:13\u201316, 1976.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Electronic Dictionaries and Automata in Computational Linguistics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51465-1_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:21:17Z","timestamp":1605630077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51465-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514657","9783540481409"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/3-540-51465-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}