Indexed by:
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 = {P-1, ..., P-d} 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. A very simple dynamic programming algorithm to this problem is presented in this paper. The correctness of the new algorithm is demonstrated. The time and space complexities of the new algorithm are both O(nmr).
Keyword:
Reprint 's Address:
Email:
Version:
Source :
GREEN, PERVASIVE, AND CLOUD COMPUTING
ISSN: 0302-9743
Year: 2016
Volume: 9663
Page: 18-29
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: