A linear algorithm for 3-letter longest common weakly increasing subsequence

作者：Duraj Lech^*

来源：Information Processing Letters, 2013, 113(3): 94-99.

DOI：10.1016/j.ipl.2012.11.007

• Algorithms
• Longest common weakly increasing
• subsequence

The problem of finding a longest weakly increasing common subsequence (LCWIS) of two sequences is a variant of the popular longest common subsequence (LCS) problem. While there are no known methods to find LCS in truly sub-quadratic time, there are faster algorithms to compute LCWIS if the alphabet size is small enough. We present a linear-time algorithm finding LCWIS over 3-letter alphabet. Up to now, the fastest known algorithm was 0 (min{m + n log n, in log log m}), where m %26gt;= n denote lengths of the sequences.

• 出版日期2013-2-15