{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T06:10:03Z","timestamp":1739167803642,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642024405"},{"type":"electronic","value":"9783642024412"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02441-2_9","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T13:19:32Z","timestamp":1245244772000},"page":"92-105","source":"Crossref","is-referenced-by-count":0,"title":["LCS Approximation via Embedding into Local Non-repetitive Strings"],"prefix":"10.1007","author":[{"given":"Gad M.","family":"Landau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"A.V. Aho","year":"1976","unstructured":"Aho, A.V., Hirschberg, D.S., Ulman, J.D.: Bounds on the complexity on the longest common subsequence problem. JACM\u00a023(1), 1\u201312 (1976)","journal-title":"JACM"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-69068-9_13","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2008","unstructured":"Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 118\u2013129. Springer, Heidelberg (2008)"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R.: The computational hardness of estimating edit distance. In: FOCS, pp.\u00a0724\u2013734 (2007)","DOI":"10.1109\/FOCS.2007.60"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"Apostolico, A., Guerra, C.: The longest common subsequence problem revisited. Algorithmica\u00a02, 315\u2013336 (1987)","journal-title":"Algorithmica"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/3-540-68530-8_7","volume-title":"Algorithms - ESA \u201998","author":"B.S. Baker","year":"1998","unstructured":"Baker, B.S., Giancarlo, R.: Longest common subsequence from fragments via sparse dynamic programming. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 79\u201390. Springer, Heidelberg (1998)"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: FOCS, pp. 550\u2013559 (2004)","DOI":"10.1109\/FOCS.2004.14"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Batu, T., Erg\u00fcn, F., Sahinalp, C.: Oblivious string embeddings and edit distance approximation. In: SODA, pp. 792\u2013801 (2006)","DOI":"10.1145\/1109557.1109644"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.4086\/toc.2006.v002a011","volume":"2","author":"M. Charikar","year":"2006","unstructured":"Charikar, M., Krauthgamer, R.: Embedding the Ulam metric into \u21131. Theory of Computing\u00a02, 207\u2013224 (2006)","journal-title":"Theory of Computing"},{"issue":"5","key":"9_CR9","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. SIAM J. Comput.\u00a032(5), 1654\u20131673 (2003)","journal-title":"SIAM J. Comput."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Porat, E.: Computing a longest increasing subsequence of length k in time o(n log log k). In: Gelenbe, E., Abramsky, S., Sassone, V. (eds.) Visions of computer science, Swindon, UK, pp. 69\u201374. The British Computer Society (2008)","DOI":"10.14236\/ewic\/VOCS2008.7"},{"key":"9_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"9_CR12","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D.S. Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. JACM\u00a024(4), 664\u2013675 (1977)","journal-title":"JACM"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J.W. Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. CACM\u00a020, 350\u2013353 (1977)","journal-title":"CACM"},{"key":"9_CR14","first-page":"125","volume":"4","author":"R. Karp","year":"1972","unstructured":"Karp, R., Miller, R., Rosenberg, A.: Rapid identification of repeated patterns in strings, arrays and trees. Symposium on the Theory of Computing\u00a04, 125\u2013136 (1972)","journal-title":"Symposium on the Theory of Computing"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"issue":"6","key":"9_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ipl.2003.09.006","volume":"88","author":"G.M. Landau","year":"2003","unstructured":"Landau, G.M., Scheiber, B., Ziv-Ukelson, M.: Sparse LCS commom substring alignment. Information Processing Letters\u00a088(6), 259\u2013270 (2003)","journal-title":"Information Processing Letters"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"G.M. Landau","year":"1988","unstructured":"Landau, G.M., Vishkin, U.: Fast string matching with k differences. Journal of Computer and System Sciences\u00a037(1), 63\u201378 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"9_CR18","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., Ziv-Ukelson, M.: On the common substring alignment problem. Journal of Algorithms\u00a041(2), 338\u2013359 (2001)","journal-title":"Journal of Algorithms"},{"key":"9_CR19","first-page":"18","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm for computing string edit distances. JCSS\u00a020, 18\u201331 (1980)","journal-title":"JCSS"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Low distortion embeddings for edit distance. In: Proceedings of the 37th annual ACM symposium on Theory of computing (STOC), pp. 218\u2013224 (2005)","DOI":"10.1145\/1060590.1060623"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"Sankoff, D.: Matching sequences under deletion\/insertion constraints. Pro. Nat. Acad. Sct. USA\u00a069, 4\u20136 (1972)","journal-title":"Pro. Nat. Acad. Sct. USA"},{"issue":"1","key":"9_CR22","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string to string correction problem. JACM\u00a021(1), 168\u2013173 (1974)","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02441-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T05:37:20Z","timestamp":1739165840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02441-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642024405","9783642024412"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02441-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}