• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Zhu, D. (Zhu, D..) [1] | Wu, Y. (Wu, Y..) [2] | Wang, X. (Wang, X..) [3]

Indexed by:

Scopus

Abstract:

In this paper, we consider a generalized longest common subsequence problem with multiple subsequence inclusive 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 length l i for each P i ∈ P, the problem is to find a common subsequence Z of X and Y including each of constraint string in P as a subsequence and the length of Z is maximized. A simple dynamic programming algorithm to this problem is presented in this paper. The correctness of the new algorithm is demonstrated. The time complexities of the new algorithm is O(nmdt), where (Formula presented.). © Springer International Publishing Switzerland 2015.

Keyword:

Dynamic programming; Longest common subsequence problem; Subsequence inclusion constraints; Time complexity

Community:

  • [ 1 ] [Zhu, D.]Quanzhou Normal University, Quanzhou, 362000, China
  • [ 2 ] [Wu, Y.]Fuzhou University, Fuzhou, 350002, China
  • [ 3 ] [Wang, X.]Fujian University of Technology, Fuzhou, 350108, China

Reprint 's Address:

  • [Wu, Y.]Fuzhou UniversityChina

Show more details

Related Keywords:

Related Article:

Source :

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISSN: 0302-9743

Year: 2015

Volume: 9502

Page: 439-446

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:292/10112749
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1