{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:26:53Z","timestamp":1725481613666},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540403111"},{"type":"electronic","value":"9783540448884"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44888-8_17","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T16:34:12Z","timestamp":1173112452000},"page":"225-236","source":"Crossref","is-referenced-by-count":4,"title":["Sparse LCS Common Substring Alignment"],"prefix":"10.1007","author":[{"given":"Gad M.","family":"Landau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,27]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"A. Apostolico, String editing and longest common subsequences. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 2, 361\u2013398, Berlin, 1997. Springer Verlag.","DOI":"10.1007\/978-3-662-07675-0_8"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"Apostolico A., and C. Guerra, The longest common subsequence problem revisited. Algorithmica, 2, 315\u2013336 (1987).","journal-title":"Algorithmica"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric Applications of a Matrix-Searching Algorithm, Algorithmica, 2, 195\u2013208 (1987).","journal-title":"Algorithmica"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/0304-3975(95)92848-R","volume":"145","author":"G. Benson","year":"1995","unstructured":"Benson, G., A space efficient algorithm for finding the best nonoverlapping alignment score, Theoretical Computer Science, 145, 357\u2013369 (1995).","journal-title":"Theoretical Computer Science"},{"key":"17_CR5","unstructured":"Crochemore, M., G.M. Landau, and M. Ziv-Ukelson, A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices, Proc. Symposium On Discrete Algorithms, 679\u2013688 (2002)."},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Z. Galil, R. Giancarlo, and G.F. Italiano, Sparse Dynamic Programming I: Linear Cost Functions, JACM, 39, 546\u2013567 (1992).","journal-title":"JACM"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Algorithms on Strings, Trees, and Sequences. Cambridge University Press, (1997).","DOI":"10.1017\/CBO9780511574931"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D.S. \u201c. Hirshberg","year":"1977","unstructured":"Hirshberg, D.S., \u201cAlgorithms for the longest common subsequence problem\u201d, JACM, 24(4), 664\u2013675 (1977).","journal-title":"JACM"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J. W. Hunt","year":"1977","unstructured":"Hunt, J. W. and T. G. Szymanski. \u201cA fast algorithm for computing longest common subsequences.\u201d Communications of the ACM, 20, 350\u2013353 (1977).","journal-title":"Communications of the ACM"},{"issue":"3","key":"17_CR10","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539794262677","volume":"25","author":"S. K. Kannan","year":"1996","unstructured":"Kannan, S. K., and E. W. Myers, An Algorithm For Locating Non-Overlapping Regions of Maximum Alignment Score, SIAM J. Comput., 25(3), 648\u2013662 (1996).","journal-title":"SIAM J. Comput"},{"key":"17_CR11","unstructured":"Landau, G.M., and M. Ziv-Ukelson, On the Shared Substring Alignment Problem, Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 804\u2013814 (2000)."},{"issue":"2","key":"17_CR12","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1006\/jagm.2001.1191","volume":"41","author":"G.M. Landau","year":"2001","unstructured":"Landau, G.M., and M. Ziv-Ukelson, On the Common Substring Alignment Problem, Journal of Algorithms, 41(2), 338\u2013359 (2001)","journal-title":"Journal of Algorithms"},{"key":"17_CR13","unstructured":"Monge, G., D\u00e9blai et Remblai, M\u00e9moires de l\u2019Academie des Sciences, Paris (1781)."},{"key":"17_CR14","unstructured":"Myers, E. W., \u201cIncremental Alignment Algorithms and their Applications,\u201d Tech. Rep. 86-22, Dept. of Computer Science, U. of Arizona. 1986."},{"issue":"4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"J.P. Schmidt","year":"1998","unstructured":"Schmidt, J.P., All Highest Scoring Paths In Weighted Grid Graphs and Their Application To Finding All Approximate Repeats In Strings, SIAM J. Comput, 27(4), 972\u2013992 (1998).","journal-title":"SIAM J. Comput"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44888-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T04:03:35Z","timestamp":1550289815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44888-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403111","9783540448884"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-44888-8_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}