جدول بندی جدید و تکنیک های مبتنی بر برنامه نویسی پویا برای حل مشکلات مشابه

Calculating the length ℓℓ of a longest common subsequence (LCS) of two strings, AA of length nn and BB of length mm, 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(mnlglgn/lg2n), O(mn/lg2n+r)O(mn/lg2n+r) and O(n+r)O(n+r) time complexity, where the second one works for r=o(mn/(lgnlglgn))r=o(mn/(lgnlglgn)), and the third one for r=Θ(mn/lgkn)r=Θ(mn/lgkn), for a real constant 1≤k≤31≤k≤3, and ℓ=O(n/(lgk−1n(lglgn)2))ℓ=O(n/(lgk−1n(lglgn)2)), where rr 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.