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.