kowalsk1's blog

LCS of distinct element sequences in O(nlg(n))
By kowalsk1, history, 6 years ago, In English

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?

Thanks ahead.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the elements are distinct we can fix one sequence, let V[i] be the i-th sequence and inV[i][j] is the position of the element with value j in the i-th sequence, the dp is straightforward i guess, dp[K] = max(dp[W] + 1 ) such that W > K && inV[1][V[0][W]] > inV[1][V[0][K]] ) or, dp[K] means the LCS of a sequence with V[0][K] as last element so we can use a segment tree with RMQ to solve this, since the restriction is inV[1][V[0][W]] > inV[1][V[0][K]] we can add dp[X] in the position inv[1][V[0][X]] and dp[Y] will be RMQ in range (inV[1][V[0][Y]] , inf)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: My mistake. Sorry.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use fenwick tree. Go from left to right in second array. For each elemnt find occurence in first array (let's say that this posision is X, this can be found with the help of maps). Now you just have to find maximum value from 1 to X-1 in our BIT which is not hard. Let's say answer is P. Than add P+1 in fenwick starting from position X.

→ Reply