{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:36Z","timestamp":1759638156890},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648482"},{"type":"electronic","value":"9783540685302"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_7","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T22:14:16Z","timestamp":1194560056000},"page":"79-90","source":"Crossref","is-referenced-by-count":3,"title":["Longest Common Subsequence from Fragments via Sparse Dynamic Programming"],"prefix":"10.1007","author":[{"given":"Brenda S.","family":"Baker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raffaele","family":"Giancarlo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"7_CR1","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, Reading, MA., 1983."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"A. Apostolico. String editing and longest common subsequence. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 2, pages 361\u2013398, Berlin, 1997. Springer Verlag.","DOI":"10.1007\/978-3-662-07675-0_8"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"B. S. Baker. A theory of parameterized pattern matching: Algorithms and applications. In Proc. 25th Symposium on Theory of Computing, pages 71\u201380. ACM, 1993.","DOI":"10.1145\/167088.167115"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo, and G. Italiano. Sparse dynamic programming I: Linear cost functions. J. of ACM, 39:519\u2013545, 1992.","journal-title":"J. of ACM"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo, and G. Italiano. Sparse dynamic programming II: Convex and concave cost functions. J. of ACM, 39:546\u2013567, 1992.","journal-title":"J. of ACM"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup. Optimal evolutionary tree comparison by sparse dynamic programming. In Proc. 35th Symposium on Foundations of Computer Science, pages 770\u2013779. IEEE, 1994.","DOI":"10.1109\/SFCS.1994.365716"},{"key":"7_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences-Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"D. Gusfield. Algorithms on Strings, Trees and Sequences-Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"D.S. Hirschberg. Serial computations of Levenshtein distances. In A. Apostolico and Z. Galil, editors, Pattern Matching Algorithms, pages 123\u2013142, Oxford, 1997. Oxford University Press.","DOI":"10.1093\/oso\/9780195113679.003.0007"},{"key":"7_CR9","doi-asserted-by":"publisher","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. Comm. of the ACM, 20:350\u2013353, 1977.","journal-title":"Comm. of the ACM"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"D. B. Johnson","year":"1982","unstructured":"D. B. Johnson. A priority queue in which initialization and queue operations take O(log logD) time. Math. Sys. Th., 15:295\u2013309, 1982.","journal-title":"Math. Sys. Th."},{"key":"7_CR11","unstructured":"J.B. Kruskal and D. Sankoff, editors. Time Wraps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, 1983."},{"key":"7_CR12","unstructured":"W. Miller and E. Myers. Chaining multiple alignment fragments in sub-quadratic time. In Proc. of 6-th ACM-SIAM SODA, pages 48\u201357, 1995."},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E. W. Myers","year":"1986","unstructured":"E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1:251\u2013266, 1986.","journal-title":"Algorithmica"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time. Info. Proc. Lett., 6:80\u201382, 1977.","journal-title":"Info. Proc. Lett."},{"key":"7_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology. Maps, Sequences and Genomes","author":"M.S. Waterman","year":"1995","unstructured":"M.S. Waterman. Introduction to Computational Biology. Maps, Sequences and Genomes. Chapman Hall, Los Angeles, 1995."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T05:29:50Z","timestamp":1630042190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}