LCS of distinct element sequences in O(nlg(n))

Revision en7, by kowalsk1, 2018-05-29 05:11:47

So here´s the problem:

Given two sequences of numbers s and r, such that all elements from the sequences are distinct, find the longest common subsequence of both sequences.

Now, i know the DP solution for the general case, which is executed in O(n2), but in this problem i need to get as efficient as O(nlg(n)). I found an explanation on stack overflow about how to use the LIS (Longest Increasing Subsequence) algorithm to achieve this complexity, but i didn´t understand very well. So does anyone how to explain a faster than quadratic algorithm to solve this problem?

History

Revisions

Rev. Lang. By When Δ Comment
en7 kowalsk1 2018-05-29 05:11:47 8 Tiny change: 'ster than squared algorithm' -> 'ster than quadratic algorithm'
en6 kowalsk1 2018-05-29 05:11:05 5 Tiny change: 'he general, which is' -> 'he general case, which is'
en5 kowalsk1 2018-05-29 05:10:35 25 (published)
en4 kowalsk1 2018-05-29 05:09:56 6 Tiny change: 'nt as $O(n*lg(n))$. I' -> 'nt as $O(n lg(n))$. I'
en3 kowalsk1 2018-05-29 05:09:25 9
en2 kowalsk1 2018-05-29 05:08:39 3 Tiny change: 'es.\n\nNow i know th' -> 'es.\n\nNow, i know th'
en1 kowalsk1 2018-05-29 05:08:09 648 Initial revision (saved to drafts)