{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:30:01Z","timestamp":1773271801416,"version":"3.50.1"},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> Given strings S<jats:sub>1<\/jats:sub>, S<jats:sub>2<\/jats:sub>, and P, the constrained longest common subsequence problem for S<jats:sub>1<\/jats:sub> and S<jats:sub>2<\/jats:sub> with respect to P is to find a longest common subsequence lcs of S<jats:sub>1<\/jats:sub> and S<jats:sub>2<\/jats:sub> which contains P as a subsequence. We present an algorithm which improves the time complexity of the problem from the previously known O(rn<jats:sup>2<\/jats:sup>m<jats:sup>2<\/jats:sup>) to O(rnm) where r, n, and m are the lengths of P, S<jats:sub>1<\/jats:sub>, and S<jats:sub>2<\/jats:sub>, respectively. As a generalization of this, we extend the definition of the problem so that the lcs sought contains a subsequence whose edit distance from P is less than a given parameter d. For the latter problem, we propose an algorithm whose time complexity is O(drnm). <\/jats:p>","DOI":"10.1142\/s0129054105003674","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1099-1109","source":"Crossref","is-referenced-by-count":45,"title":["ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS"],"prefix":"10.1142","volume":"16","author":[{"given":"ABDULLAH N.","family":"ARSLAN","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Vermont, Burlington, VT 05405, USA"}]},{"given":"\u00d6MER","family":"E\u011eECIO\u011eLU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA 93106, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"1","volume":"23","author":"Aho A. V.","journal-title":"J. ACM"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.008"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.001"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:03Z","timestamp":1565191743000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":7,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003674"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003674","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}