New tabulation and sparse dynamic programming based techniques for sequence similarity problems

Calculating the length ℓ of a longest common subsequence (LCS) of two strings, A of length n and B of length m, is a classic research topic, with many known worst-case oriented results. We present three algorithms for LCS length calculation with respectively O(mnlglgn/lg2n), O(mn/lg2n+r) and O(n+r) time complexity, where the second one works for r=o(mn/(lgnlglgn)), and the third one for r=Θ(mn/lgkn), for a real constant 1≤k≤3, and ℓ=O(n/(lgk−1n(lglgn)2)), where r is the number of matches in the dynamic programming matrix. We also describe conditions for a given problem sufficient to apply our techniques, with several concrete examples presented, namely the edit distance, the longest common transposition-invariant subsequence (LCTS) and the merged longest common subsequence (MerLCS) problems.