{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:43:51Z","timestamp":1725515031913},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540728689"},{"type":"electronic","value":"9783540728702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72870-2_8","type":"book-chapter","created":{"date-parts":[[2007,6,25]],"date-time":"2007-06-25T12:53:10Z","timestamp":1182775990000},"page":"82-90","source":"Crossref","is-referenced-by-count":1,"title":["A New Efficient Algorithm for Computing the Longest Common Subsequence"],"prefix":"10.1007","author":[{"given":"M. Sohel","family":"Rahman","sequence":"first","affiliation":[]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1975","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economic construction of the transitive closure of a directed graph (english translation). Soviet Math. Dokl.\u00a011, 1209\u20131210 (1975)","journal-title":"Soviet Math. Dokl."},{"issue":"6","key":"8_CR2","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"A.N. Arslan","year":"2005","unstructured":"Arslan, A.N., Egecioglu, \u00d6.: Algorithms for the constrained longest common subsequence problems. Int. J. Found. Comput. Sci.\u00a016(6), 1099\u20131109 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: SPIRE, pp. 39\u201348 (2000)","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"8_CR5","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. In: Symposium of Discrete Algorithms (SODA), pp. 679\u2013688 (2002)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Gabow, H., Bentley, J., Tarjan, R.: Scaling and related techniques for geometry problems. In: STOC, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"8_CR7","first-page":"263","volume":"61","author":"F. Hadlock","year":"1988","unstructured":"Hadlock, F.: Minimum detour methods for string or sequence comparison. Congressus Numerantium\u00a061, 263\u2013274 (1988)","journal-title":"Congressus Numerantium"},{"issue":"4","key":"8_CR8","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. J. ACM\u00a024(4), 664\u2013675 (1977)","journal-title":"J. ACM"},{"issue":"5","key":"8_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., Szymanski, T.G.: A fast algorithm for computing longest subsequences. Commun. ACM\u00a020(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"issue":"5","key":"8_CR10","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM Journal of Computing\u00a024(5), 1122\u20131139 (1995)","journal-title":"SIAM Journal of Computing"},{"key":"8_CR11","first-page":"8","volume":"1","author":"V.I. Levenshtein","year":"1965","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Problems in Information Transmission\u00a01, 8\u201317 (1965)","journal-title":"Problems in Information Transmission"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/11496656_2","volume-title":"Combinatorial Pattern Matching","author":"B. Ma","year":"2005","unstructured":"Ma, B., Zhang, K.: On the longest common rigid subsequence problem. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 11\u201320. Springer, Heidelberg (2005)"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. Journal of the ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"issue":"1","key":"8_CR14","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci.\u00a020(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"8_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"Myers, E.W.: An o(nd) difference algorithm and its variations. Algorithmica\u00a01(2), 251\u2013266 (1986)","journal-title":"Algorithmica"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N. Nakatsu","year":"1982","unstructured":"Nakatsu, N., Kambayashi, Y., Yajima, S.: A longest common subsequence algorithm suitable for similar text strings. Acta Inf.\u00a018, 171\u2013179 (1982)","journal-title":"Acta Inf."},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/11940128_41","volume-title":"Algorithms and Computation","author":"M.S. Rahman","year":"2006","unstructured":"Rahman, M.S., Iliopoulos, C.S.: Algorithms for computing variants of the longest common subsequence problem. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 399\u2013408. Springer, Heidelberg (2006)"},{"issue":"4","key":"8_CR18","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"Y.-T. Tsai","year":"2003","unstructured":"Tsai, Y.-T.: The constrained longest common subsequence problem. Inf. Process. Lett.\u00a088(4), 173\u2013176 (2003)","journal-title":"Inf. Process. Lett."},{"key":"8_CR19","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":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"issue":"1","key":"8_CR20","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. J. ACM\u00a021(1), 168\u2013173 (1974)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72870-2_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:07:24Z","timestamp":1605762444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72870-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540728689","9783540728702"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72870-2_8","relation":{},"subject":[]}}