{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:04:15Z","timestamp":1761807855660,"version":"build-2065373602"},"reference-count":10,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T00:00:00Z","timestamp":1376524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper studies the string-excluding (STR-EC)-constrained longest common subsequence (LCS) problem, a generalized LCS problem. For the two input sequences, X and Y , of lengths n andmand a constraint string, P, of length r, the goal is to find the longest common subsequence, Z, of X and Y that excludes P as a substring. The problem and its solution were first proposed by Chen and Chao, but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper, and the correctness of the new algorithm is proven. The time complexity of the new algorithm is O(nmr).<\/jats:p>","DOI":"10.3390\/a6030485","type":"journal-article","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T02:05:47Z","timestamp":1376618747000},"page":"485-493","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Simple Algorithm for Solving for the Generalized Longest Common Subsequence (LCS) Problem with a Substring Exclusion Constraint"],"prefix":"10.3390","volume":"6","author":[{"given":"Daxin","family":"Zhu","sequence":"first","affiliation":[{"name":"Faculty of Mathematics & Computer Science, Quanzhou Normal University, Quanzhou 362000, China"}]},{"given":"Xiaodong","family":"Wang","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics & Computer Science, Quanzhou Normal University, Quanzhou 362000, China"},{"name":"Faculty of Mathematics & Computer Science, Fuzhou University, Fuzhou 350108, China"}]}],"member":"1968","published-online":{"date-parts":[[2013,8,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0219720003000095","article-title":"Constrained multiple sequence alignment tool development and its application to RNase family alignment","volume":"1","author":"Tang","year":"2003","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","article-title":"The constrained longest common subsequence problem","volume":"88","author":"Tsai","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_3","first-page":"427","article-title":"Constrained longest common subsequence computing algorithms in practice","volume":"29","author":"Deorowicz","year":"2010","journal-title":"Comput. Inf."},{"key":"ref_4","first-page":"355","article-title":"A new efficient algorithm for computing the longest common subsequence","volume":"45","author":"Iliopoulos","year":"2009","journal-title":"Theory Comput. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1142\/S012905411000712X","article-title":"An algorithm and applications to sequence alignment with weighted constraints","volume":"21","author":"Peng","year":"2010","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Hermelin, D., Landau, G.M., and Lewenstein, M. (2010, January 11\u201313). Restricted LCS. Proceedings of the 17th International Conference on String Processing and Information Retrieval, SPIRE\u201910, Los Cabos, Mexico.","DOI":"10.1007\/978-3-642-16321-0_26"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10878-009-9262-5","article-title":"On the generalized constrained longest common subsequence problems","volume":"21","author":"Chen","year":"2011","journal-title":"J. Comb. Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.ipl.2012.02.007","article-title":"Quadratic-time algorithm for a string constrained LCS problem","volume":"112","author":"Deorowicz","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.jco.2012.08.002","article-title":"Efficient algorithms for the longest common subsequence problem with sequential substring constraints","volume":"29","author":"Tseng","year":"2013","journal-title":"J. Complex."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/485\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:48:39Z","timestamp":1760219319000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,15]]},"references-count":10,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,9]]}},"alternative-id":["a6030485"],"URL":"https:\/\/doi.org\/10.3390\/a6030485","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,8,15]]}}}