{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:59:45Z","timestamp":1725854385347},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319390765"},{"type":"electronic","value":"9783319390772"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-39077-2_2","type":"book-chapter","created":{"date-parts":[[2016,5,2]],"date-time":"2016-05-02T13:00:15Z","timestamp":1462194015000},"page":"18-29","source":"Crossref","is-referenced-by-count":1,"title":["A Polynomial Time Algorithm for a Generalized Longest Common Subsequence Problem"],"prefix":"10.1007","author":[{"given":"Xiaodong","family":"Wang","sequence":"first","affiliation":[]},{"given":"Yingjie","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Daxin","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,3]]},"reference":[{"issue":"6","key":"2_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"issue":"11","key":"2_CR2","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.ipl.2008.07.005","volume":"108","author":"HY Ann","year":"2008","unstructured":"Ann, H.Y., Yang, C.B., Tseng, C.T., Hor, C.Y.: A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings. Inform. Process Lett. 108(11), 360\u2013364 (2008)","journal-title":"Inform. Process Lett."},{"issue":"3","key":"2_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.ic.2009.12.001","volume":"208","author":"HY Ann","year":"2010","unstructured":"Ann, H.Y., Yang, C.B., Peng, Y.H., Liaw, B.C.: Efficient algorithms for the block edit problems. Inf. Comput. 208(3), 221\u2013229 (2010)","journal-title":"Inf. Comput."},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A Apostolico","year":"1987","unstructured":"Apostolico, A., Guerra, C.: The longest common subsequences problem revisited. Algorithmica 2(1), 315\u2013336 (1987)","journal-title":"Algorithmica"},{"issue":"6","key":"2_CR5","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"AN Arslan","year":"2005","unstructured":"Arslan, A.N., Egecioglu, O.: Algorithms for the constrained longest common subsequence problems. Int. J. Found. Comput. Sci. 16(6), 1099\u20131109 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"12","key":"2_CR6","doi-asserted-by":"publisher","first-page":"3178","DOI":"10.1016\/j.cor.2009.02.005","volume":"36","author":"C Blum","year":"2009","unstructured":"Blum, C., Blesa, M.J., Lpez-Ibnez, M.: Beam search for the longest common subsequence problem. Comput. Oper. Res. 36(12), 3178\u20133186 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"2_CR7","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10878-009-9262-5","volume":"21","author":"YC Chen","year":"2011","unstructured":"Chen, Y.C., Chao, K.M.: On the generalized constrained longest common subsequence problems. J. Comb. Optim. 21(3), 383\u2013392 (2011)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"2_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.ipl.2004.02.008","volume":"90","author":"FYL Chin","year":"2004","unstructured":"Chin, F.Y.L., Santis, A.D., Ferrara, A.L., Ho, N.L., Kim, S.K.: A simple algorithm for the constrained sequence problems. Inform. Process. Lett. 90(4), 175\u2013179 (2004)","journal-title":"Inform. Process. Lett."},{"key":"2_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge, UK (2007)"},{"issue":"11","key":"2_CR10","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.ipl.2012.02.007","volume":"112","author":"S Deorowicz","year":"2012","unstructured":"Deorowicz, S.: Quadratic-time algorithm for a string constrained LCS problem. Inform. Process. Lett. 112(11), 423\u2013426 (2012)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"2_CR11","first-page":"427","volume":"29","author":"S Deorowicz","year":"2010","unstructured":"Deorowicz, S., Obstoj, J.: Constrained longest common subsequence computing algorithms in practice. Comput. Inform. 29(3), 427\u2013445 (2010)","journal-title":"Comput. Inform."},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-16321-0_25","volume-title":"String Processing and Information Retrieval","author":"E Farhana","year":"2010","unstructured":"Farhana, E., Ferdous, J., Moosa, T., Rahman, M.S.: Finite automata based algorithms for the generalized constrained longest common subsequence problems. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 243\u2013249. Springer, Heidelberg (2010)"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-540-69068-9_24","volume-title":"Combinatorial Pattern Matching","author":"Z Gotthilf","year":"2008","unstructured":"Gotthilf, Z., Hermelin, D., Lewenstein, M.: Constrained LCS: hardness and approximation. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 255\u2013262. Springer, Heidelberg (2008)"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-16321-0_26","volume-title":"String Processing and Information Retrieval","author":"Z Gotthilf","year":"2010","unstructured":"Gotthilf, Z., Hermelin, D., Landau, G.M., Lewenstein, M.: Restricted LCS. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 250\u2013257. Springer, Heidelberg (2010)"},{"key":"2_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"2_CR16","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM 24(4), 664\u2013675 (1977)","journal-title":"J. ACM"},{"issue":"5","key":"2_CR17","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"issue":"1","key":"2_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2007.09.008","volume":"106","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Rahman, M.S.: New efficient algorithms for the LCS and constrained LCS problems. Inform. Process. Lett. 106(1), 13\u201318 (2008)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"2_CR19","first-page":"355","volume":"45","author":"CS Iliopoulos","year":"2009","unstructured":"Iliopoulos, C.S., Rahman, M.S.: A new efficient algorithm for computing the longest common subsequence. Theor. Comput. Sci. 45(2), 355\u2013371 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR20","first-page":"155","volume":"71","author":"CS Iliopoulos","year":"2009","unstructured":"Iliopoulos, C.S., Rahman, M.S., Rytter, W.: Algorithms for two versions of LCS problem for indeterminate strings. J. Comb. Math. Comb. Comput. 71, 155\u2013172 (2009)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"2","key":"2_CR21","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.jda.2008.10.004","volume":"8","author":"CS Iliopoulos","year":"2010","unstructured":"Iliopoulos, C.S., Rahman, M.S., Vorcek, M., Vagner, L.: Finite automata based algorithms on subsequences and supersequences of degenerate strings. J. Discrete Algorithm 8(2), 117\u2013130 (2010)","journal-title":"J. Discrete Algorithm"},{"issue":"2","key":"2_CR22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"2_CR23","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. J. ACM 25, 322\u2013336 (1978)","journal-title":"J. ACM"},{"issue":"1","key":"2_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1142\/S012905411000712X","volume":"21","author":"YH Peng","year":"2010","unstructured":"Peng, Y.H., Yang, C.B., Huang, K.S., Tseng, K.T.: An algorithm and applications to sequence alignment with weighted constraints. Int. J. Found. Comput. Sci. 21(1), 51\u201359 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"2_CR25","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.cor.2007.07.006","volume":"36","author":"SJ Shyu","year":"2009","unstructured":"Shyu, S.J., Tsai, C.Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1), 73\u201391 (2009)","journal-title":"Comput. Oper. Res."},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0219720003000095","volume":"1","author":"CY Tang","year":"2003","unstructured":"Tang, C.Y., Lu, C.L.: Constrained multiple sequence alignment tool development and its application to RNase family alignment. J. Bioinform. Comput. Biol. 1, 267\u2013287 (2003)","journal-title":"J. Bioinform. Comput. Biol."},{"issue":"4","key":"2_CR27","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"YT Tsai","year":"2003","unstructured":"Tsai, Y.T.: The constrained longest common subsequence problem. Inform. Process. Lett. 88(4), 173\u2013176 (2003)","journal-title":"Inform. Process. Lett."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.jco.2012.08.002","volume":"29","author":"CT Tseng","year":"2013","unstructured":"Tseng, C.T., Yang, C.B., Ann, H.Y.: Efficient algorithms for the longest common subsequence problem with sequential substring constraints. J. Complex. 29, 44\u201352 (2013)","journal-title":"J. Complex."},{"issue":"1","key":"2_CR29","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R Wagner","year":"1974","unstructured":"Wagner, R., Fischer, M.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"issue":"1","key":"2_CR30","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/j.ipl.2013.07.005","volume":"113","author":"L Wang","year":"2013","unstructured":"Wang, L., Wang, X., Wu, Y., Zhu, D.: A dynamic programming solution to a generalized LCS problem. Inform. Process. Lett. 113(1), 723\u2013728 (2013)","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Green, Pervasive, and Cloud Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-39077-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T02:32:27Z","timestamp":1559442747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-39077-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319390765","9783319390772"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-39077-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}