{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:33:02Z","timestamp":1773271982984,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,8,27]],"date-time":"2009-08-27T00:00:00Z","timestamp":1251331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s10878-009-9262-5","type":"journal-article","created":{"date-parts":[[2009,8,26]],"date-time":"2009-08-26T14:21:58Z","timestamp":1251296518000},"page":"383-392","source":"Crossref","is-referenced-by-count":55,"title":["On the generalized constrained longest common subsequence problems"],"prefix":"10.1007","volume":"21","author":[{"given":"Yi-Ching","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,8,27]]},"reference":[{"key":"9262_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"AV Aho","year":"1976","unstructured":"Aho AV, Hirschberg DS, Ullman JD (1976) Bounds on the complexity of the longest common subsequence problem. J\u00a0ACM 23:1\u201312","journal-title":"J\u00a0ACM"},{"key":"9262_CR2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A Apostolico","year":"1987","unstructured":"Apostolico\u00a0A, Guerra\u00a0C (1987) The longest common subsequence problem revisited. Algorithmica 2:315\u2013336","journal-title":"Algorithmica"},{"issue":"6","key":"9262_CR3","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"AN Arslan","year":"2005","unstructured":"Arslan AN, E\u01e7ecio\u01e7lu\u00a0O (2005) Algorithms for the constrained longest common subsequence problems. Int J\u00a0Found Comput Sci 16(6):1099\u20131109","journal-title":"Int J\u00a0Found Comput Sci"},{"key":"9262_CR4","doi-asserted-by":"crossref","unstructured":"Bergroth\u00a0L, Hakonen\u00a0H, Raita\u00a0T (2000) A survey of longest common subsequence algorithms. In: Proceedings of the 7th international symposium on string processing and information retrieval (SPIRE\u201900), pp 39\u201348","DOI":"10.1109\/SPIRE.2000.878178"},{"issue":"4","key":"9262_CR5","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1109\/TCBB.2007.1066","volume":"4","author":"P Bonizzoni","year":"2007","unstructured":"Bonizzoni\u00a0P, Vedova GD, Dondi\u00a0R, Fertin\u00a0G, Rizzi\u00a0R, Vialette\u00a0S (2007) Exemplar longest common subsequence. IEEE Trans Comput Biol Bioinform 4(4):535\u2013543","journal-title":"IEEE Trans Comput Biol Bioinform"},{"key":"9262_CR6","volume-title":"Sequence comparison: theory and methods","author":"KM Chao","year":"2009","unstructured":"Chao KM, Zhang\u00a0L (2009) Sequence comparison: theory and methods. Springer, Berlin"},{"key":"9262_CR7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.ipl.2004.02.008","volume":"90","author":"FYL Chin","year":"2004","unstructured":"Chin FYL, Santis AD, Ferrara AL, Ho NL, Kim SK (2004) A simple algorithm for the constrained longest common sequence problems. Inf Process Lett 90:175\u2013179","journal-title":"Inf Process Lett"},{"issue":"1","key":"9262_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0219720005000977","volume":"3","author":"FYL Chin","year":"2005","unstructured":"Chin FYL, Ho NL, Lam TW, Wong PWH (2005) Efficient constrained multiple sequence alignment with performance guarantee. J\u00a0Bioinform Comput Biol 3(1):1\u201318","journal-title":"J\u00a0Bioinform Comput Biol"},{"key":"9262_CR9","first-page":"350","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein\u00a0C (2001). In: Introduction to algorithms, 2nd edn. MIT Press\/McGraw-Hill, New York, pp 350\u2013355.","edition":"2"},{"key":"9262_CR10","doi-asserted-by":"crossref","unstructured":"Gotthilf\u00a0Z, Hermelin\u00a0D, Lewenstein\u00a0M (2008) Constrained LCS: hardness and approximation. In: Proceedings of the 19th annual symposium on combinatorial pattern matching (CPM\u201908), pp 255\u2013262","DOI":"10.1007\/978-3-540-69068-9_24"},{"key":"9262_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences","author":"D Gusfield","year":"1997","unstructured":"Gusfield\u00a0D (1997) Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge"},{"key":"9262_CR12","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS (1975) A linear space algorithm for computing maximal common subsequences. Commun ACM 18:341\u2013343","journal-title":"Commun ACM"},{"key":"9262_CR13","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg DS (1977) Algorithms for the longest common subsequence problem. J\u00a0ACM 24:664\u2013675","journal-title":"J\u00a0ACM"},{"issue":"5","key":"9262_CR14","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt JW, Szymanski TG (1977) A fast algorithm for computing longest common subsequence. Commun ACM 20(5):350\u2013353","journal-title":"Commun ACM"},{"key":"9262_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ipl.2007.09.008","volume":"106","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos CS, Rahman MS (2008) New efficient algorithms for the LCS and constrained LCS problems. Inf Process Lett 106:13\u201318","journal-title":"Inf Process Lett"},{"key":"9262_CR16","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier\u00a0D (1978) The complexity of some problems on subsequences and supersequence. J\u00a0ACM 25:322\u2013336","journal-title":"J\u00a0ACM"},{"key":"9262_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek WJ, Paterson MS (1980) A faster algorithm computing string edit distances. J\u00a0Comput Syst Sci 20:18\u201331","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9262_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational molecular biology: An algorithmic approach","author":"PA Pevzner","year":"2000","unstructured":"Pevzner PA (2000) Computational molecular biology: An algorithmic approach. MIT Press, Cambridge"},{"key":"9262_CR19","unstructured":"Rahman MS, Iliopoulos CS (2007) A new efficient algorithm for computing the longest common subsequence. In: Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM\u201907), pp 82\u201390"},{"issue":"2","key":"9262_CR20","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0219720003000095","volume":"1","author":"CY Tang","year":"2003","unstructured":"Tang CY, Lu CL, Chang MD, Tsai YT, Sun YJ, Chao KM, Chang JM, Chiou YH, Wu CM, Chang HT, Chou WI (2003) Constrained multiple sequence alignment tool development and its application to RNase family alignment. J\u00a0Bioinform Comput Biol 1(2):267\u2013287","journal-title":"J\u00a0Bioinform Comput Biol"},{"key":"9262_CR21","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"YT Tsai","year":"2003","unstructured":"Tsai YT (2003) The constrained longest common subsequence problem. Inf Process Lett 88:173\u2013176","journal-title":"Inf Process Lett"},{"key":"9262_CR22","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P Emde Boas van","year":"1977","unstructured":"van Emde Boas\u00a0P (1977) Preserving order in a forest in less than logarithmic time and linear space. Inf Process Lett 6:80\u201382","journal-title":"Inf Process Lett"},{"key":"9262_CR23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P Emde Boas van","year":"1977","unstructured":"van Emde Boas\u00a0P, Kaas\u00a0R, Zijlstra\u00a0E (1977) Design and implementation of an efficient priority queue. Math Syst Theory 10:99\u2013127","journal-title":"Math Syst Theory"},{"issue":"1","key":"9262_CR24","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner RA, Fischer MJ (1974) The string-to-string correction problem. J\u00a0ACM 21(1):168\u2013173","journal-title":"J\u00a0ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9262-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9262-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9262-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:15Z","timestamp":1559261895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9262-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,27]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9262"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9262-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,27]]}}}