New tabulation and sparse dynamic programming based techniques for sequence similarity problems
Grabowski, Szymon
Original · EN
Calculating the length of a longest common subsequence (LCS) of two strings A and B of length n and m is a classic research topic, with many worst-case oriented results known. We present two algorithms for LCS length calculation with respectively O(mn n / ² n) and O(mn / ² n + r) time complexity, the latter working for r = o(mn / (n n)), 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, LCTS and MerLCS problems.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.