{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T18:25:10Z","timestamp":1637605510723},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[1977,5]]},"abstract":"\n Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n\n 2<\/jats:sup>\n ). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n\n 2<\/jats:sup>\n log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.\n <\/jats:p>","DOI":"10.1145\/359581.359603","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:34:59Z","timestamp":1027769699000},"page":"350-353","source":"Crossref","is-referenced-by-count":367,"title":["A fast algorithm for computing longest common subsequences"],"prefix":"10.1145","volume":"20","author":[{"given":"James W.","family":"Hunt","sequence":"first","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]},{"given":"Thomas G.","family":"Szymanski","sequence":"additional","affiliation":[{"name":"Princeton Univ., Princeton, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","volume-title":"Calif.","author":"Chvatal V.","year":"1972"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.26"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_1_5_2","author":"Szymansld T.G.","year":"1975","journal-title":"Eng., Princeton U., Princeton, N.J."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_2_1_7_2","volume-title":"Ill.","author":"Yao A.C.","year":"1975"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/359581.359603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,3]],"date-time":"2021-03-03T14:31:00Z","timestamp":1614781860000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,5]]},"references-count":7,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1977,5]]}},"alternative-id":["10.1145\/359581.359603"],"URL":"http:\/\/dx.doi.org\/10.1145\/359581.359603","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":["General Computer Science"],"published":{"date-parts":[[1977,5]]}}}