An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints - Details

author：

Wu, Yingjie (Wu, Yingjie.) ^[1] | Wang, Lei (Wang, Lei.) ^[2] | Zhu, Daxin (Zhu, Daxin.) ^[3] | Wang, Xiaodong (Wang, Xiaodong.) ^[4]

Indexed by：

EI Scopus

Abstract：

In　this　paper,　we　consider　a　generalized　longest　common　subsequence　problem　with　multiple　substring　exclusive　constraints.　For　the　two　input　sequences　X　and　Y　of　lengths　n　and　m,　and　a　set　of　d　constraints　P={P1,...,　Pd}　of　total　length　r,　the　problem　is　to　find　a　common　subsequence　Z　of　X　and　Y　excluding　each　of　constraint　string　in　P　as　a　substring　and　the　length　of　Z　is　maximized.　The　problem　was　declared　to　be　NP-hard　[7],　but　we　finally　found　that　this　is　not　true.　A　new　dynamic　programming　solution　for　this　problem　is　presented　in　this　paper.　The　correctness　of　the　new　algorithm　is　proved.　The　time　complexity　of　our　algorithm　is　O(nmr).　©　2014　Elsevier　B.V.

Keyword：

Algorithms Computational complexity Dynamic programming

Community：

[ 1 ] [Wu, Yingjie]Faculty of Mathematics and Computer Science, Fuzhou University, China
[ 2 ] [Wang, Lei]Microsoft AdCenter, Bellevue, WA 98004, United States
[ 3 ] [Zhu, Daxin]Faculty of Mathematics and Computer Science, Quanzhou Normal University, China
[ 4 ] [Wang, Xiaodong]Faculty of Mathematics and Computer Science, Quanzhou Normal University, China
[ 5 ] [Wang, Xiaodong]Faculty of Mathematics and Computer Science, Fuzhou University, China