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 A of length n n and B B of length m 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 ( m n lg lg n / lg 2 n ) , O(mn/lg2n+r) O ( m n / lg 2 n + r ) and O(n+r) O ( n + r ) time complexity, where the second one works for r=o(mn/(lgnlglgn)) r = o ( m n / ( lg n lg lg n ) ) , and the third one for r=?(mn/lgkn) r = ? ( m n / lg k n ) , for a real constant 1?k?3 1 ? k ? 3 , and ?=O(n/(lgk?1n(lglgn)2)) ? = O ( n / ( lg k ? 1 n ( lg lg n ) 2 ) ) , where r 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.
tabulation sparse dynamic programming sequence similarity longest common subsequence