Jim_Moriarty_'s blog

Help -LCS of two distinct element sequences in O(nlog(n))
By Jim_Moriarty_, history, 4 years ago, In English

Two sequences A and B each of which consist of distinct elements . Find the lcs of two sequences. I have read an explanation on stack overflow but I was not able to understand. Please help with this...

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

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hint: If $$$A = [1, 2, 3, ..., N]$$$, then it's easy to see that you have to compute the longest increasing subsequence of $$$B$$$.

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

It can be solved using segment tree. If the numbers are not in the range 1 ~ N then compress the array.
see this problem

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

Solution -
Precompute the indexes for all A[i] and store in a map.
We maintain a res[] array, where res[i] contains the result when we consider B[i] to be the last element of our LCS.
Iterate the sequence B, for each B[i] :
1) If there is no appearance of B[i] in A, skip that element.
2) Now considering this position to be the last for our LCS, only those B[i]'s can contribute to the LCS, whose value in A have appeared before the index where our current value is present in A(which is map[B[x]]).
Then for our current position(i.e. x), res[x] = max(res[0, 1, ... map[B[x]] — 1]) + 1.
So as to calculate the res[x], we need a BIT/Seg tree (coz we need to update and do max range queries).

Soln

→ Reply