科研之友
微信
新浪微博
Facebook
分享链接
摘要
Calculating the length l 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(mn 1g 1g n/ lg(2) n), O(mn/ lg(2) n + r) and O(n + r) time complexity, where the second one works for r = o(mn/(lg n lg lg n)), and the third one for r = Theta(mn/ lg(k) n), for a real constant 1 <= k <= 3, and l = O(n/(lg(k-1) n(lg lg n)(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.
- 出版日期2016-10-30
