||Given two strings A = a1a2a3...am and B = b1b2b3...bn, the longest|
common subsequence (LCS) problem is that of finding the longest common
part of A and B by deleting zero or more characters from A and B. Given
a string S = a1a2a3...am, composed of comparable elements, the longest
increasing subsequence (LIS) problem is that of finding a subsequence of
S such that the subsequence is increasing and its length is maximal. The
constrained LCS (CLCS) or constrained LIS (CLIS) problem is that of finding
the longest subsequence satisfying the given constraint C. In this dissertation,
we propose and solve several variants of the LCS and LIS problems, which
are (1) the sequential substring CLCS problem, (2) the string-exclusion
CLCS problem, (3) the minimum height LIS problem and (4) the sequence
constrained LIS problem.
Given an ordered set of constraint substrings (C^1, C^2,... , C^h) with
total length r, the sequential substring CLCS problem is that of finding the
CLCS of A and B containing all constraint substrings as substrings and the
order of them are retained. This problem has two variants, depending on
whether the strings cannot overlap or may overlap. We propose algorithms
with O(mnh + (m + n)(|Σ| + r)) and O(mnr + (m + n)|Σ|) time for the two
variants, respectively. When there is a single constraint substring, i.e., the
string-inclusion CLCS problem, our algorithm runs in O(mn+(m+n)(|Σ|+r))
time which improves the previous O(mnr)-time algorithm.
The string-exclusion CLCS is that of finding the LCS excluding C as a
substring. We propose an O(mnr)-time algorithm for it even if there are
multiple constraints with total length r.
The minimum height LIS problem is that of finding the ones with minimum
difference between the first element and the last element among the LIS's.
We propose an algorithm with O(n log n)-time and O(n)-space to solve it.
The sequence constrained LIS problem is that of finding the CLIS of A
containing C. We propose two variants of this problem, without or with
preprocessing. We solve the first one with time complexity O(n log(n + |C|)).
For the second one, after an O(n^2 log log n)-time preprocessing, we can answer one query in O(|C| + |OUTPUT|) time where OUTPUT is the answer to the query.