论文标题
最长常见的子序列问题的更快的亚属算法
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
论文作者
论文摘要
最长的共同增加子序列（LCI）是经典最长共同子序列（LCS）的变体，其中我们还要求严格增加共同的子序列。虽然著名的“四个俄罗斯人”技术可用于在次级时期找到LCS，但它似乎不适用于LCIS。最近，Duraj [STACS 2020]使用了基于LCI的组合属性的完全不同的方法来设计$ \ Mathcal {o}（n^2（\ log \ log \ log \ log n）^2/\ log^{1/6} n）$ time Algorithm。我们表明，基于利用制表的方法可用于构造渐近$ \ MATHCAL {O}（n^2 \ log \ log \ log \ log n/\ sqrt {\ log n}）$ time AlgorithM。由于我们的解决方案避免使用LCI的特定组合特性，因此它也可以适用于最长常见的弱增加子序列（LCWIS）。
The Longest Common Increasing Subsequence (LCIS) is a variant of the classical Longest Common Subsequence (LCS), in which we additionally require the common subsequence to be strictly increasing. While the well-known "Four Russians" technique can be used to find LCS in subquadratic time, it does not seem applicable to LCIS. Recently, Duraj [STACS 2020] used a completely different method based on the combinatorial properties of LCIS to design an $\mathcal{O}(n^2(\log\log n)^2/\log^{1/6}n)$ time algorithm. We show that an approach based on exploiting tabulation can be used to construct an asymptotically faster $\mathcal{O}(n^2 \log\log n/\sqrt{\log n})$ time algorithm. As our solution avoids using the specific combinatorial properties of LCIS, it can be also adapted for the Longest Common Weakly Increasing Subsequence (LCWIS).
