返回Google圖書搜尋

A Faster Algorithm for Computing a Longest Common Increasing Subsequence

出版	Max-Planck-Institut für Informatik, 2005
URL	http://books.google.com.hk/books?id=fwkntwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Let A = a1 ..., a[subscript n] and B = b1 ..., b[subscript m] be two sequences with m [> or =] n, whose elements are drawn from a totally ordered set. We present an algorithm that finds a longest common increasing subsequence of A and B in O(m log m + nl log n) time and O(m + nl) space, where l is the length of the output. A previous algorithm by Yang et al. needs [theta](mn) time and space, so ours is faster for a wide range of values of m, n and l."