Abstract
The longest common increasing subsequence (LCIS) problem is the combination of two classic problems in algorithms: the longest increasing subsequence (LIS) problem and the longest common subsequence (LCS) problem. In this paper, we propose an algorithm that finds every LCIS of two sequences a, b of length n in O(n+ σ+ I a ) time and space, where σ denotes the size of the alphabet set and I a the total number of increasing subsequences contained in a (thus, the running time is output-sensitive). Our algorithm employs the trie and some simple data structures, and thus is implementation-wise simple. In addition, it can be proved that our algorithm is optimal in time complexity when σ≤ log 2 n.