We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths m and n, where m ≥ n, we present an algorithm with an output-dependent expected running time of O((m + nf) log log σ + Sort) and O(m) space, where l is the length of an LCIS, σ is the size of the alphabet, and Sort is the time to sort each input sequence. For k ≥ 3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an O(m + n log n)-time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.
展开▼
机译：我们提出了用于找到两个或多个输入序列的最长公共递增子序列的算法。对于长度为m和n的两个序列，其中m≥n，我们提出一种算法，其输出依赖的预期运行时间为O（（m + nf）log logσ+ Sort）和O（m）空间，其中l为LCIS的长度，σ是字母的大小，而Sort是对每个输入序列进行排序的时间。对于k≥3个长度为n的序列，我们提出了一种算法，该算法将许多输入的先前最佳边界提高了k倍以上。在这两种情况下，我们的算法在概念上都很简单，但是依赖于现有的复杂数据结构。最后，我们介绍了最长的普通弱增（或不减）子序列（LCWIS）的问题，为此，我们针对三字母字母的情况提出了O（m + n log n）时间算法。对于经过广泛研究的最长公共子序列问题，对于小字母，尚未实现可比的加速。
展开▼
