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

author:

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

Indexed by:

CPCI-S EI 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 is an element of 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 t = Pi(1 <= i <= d) l(i).

Keyword:

Dynamic programming Longest common subsequence problem Subsequence inclusion constraints Time complexity

Community:

  • [ 1 ] [Zhu, Daxin]Quanzhou Normal Univ, Quanzhou 362000, Peoples R China
  • [ 2 ] [Wu, Yingjie]Fuzhou Univ, Fuzhou 350002, Peoples R China
  • [ 3 ] [Wang, Xiaodong]Fujian Univ Technol, Fuzhou 350108, Peoples R China

Reprint 's Address:

  • 吴英杰

    [Wu, Yingjie]Fuzhou Univ, Fuzhou 350002, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

Source :

INTERNET OF VEHICLES - SAFE AND INTELLIGENT MOBILITY, IOV 2015

ISSN: 0302-9743

Year: 2015

Volume: 9502

Page: 439-446

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Online/Total:115/10110753
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