ybc_c's blog

A Question about A Special LCS Problem
By ybc_c, 10 years ago, In English

Hi All :-)

I think some of you may read this problem from hackerrank. Here is the link:

https://www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence

Since the test data is so weak, the traditional O(mn) solution can pass all the test data. So let's assume the two strings can be as long as 10^5. In this case, how to solve this problem? I guess the time complexity of the solution should be O(500*10^5) but have no idea to code it ... :-(

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

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

Deleted

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

I think Hirschberg algorithm can be implemented in O(n*n*log(n)) time and O(n) space. But I don't know is it enough to get AC because i don't know time limit
Function int solveLCS(String x, String y) should return whole vector K[1]. And instead of

c1 = solveLCS( x1, y.substring(0, k) ) ; // LCS of first half
c2 = solveLCS( x2, y.substring(k, n) ) ; // LCS of second half

if ( c1 + c2 == c )

there should be

c1 = solveLCS( x1, y) ; // LCS of first half
c2 = solveLCS( x2.reverse(), y.reverse() ) ; // LCS of second half

if ( c1[k] + c2[n - k] == c )
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    wikipedia say's there is O(n*m) implementation of Hirschberg algorithm.
    UPD: I was wrong. My algorithm also takes O(n*m) time, without Log(n) multiplier.

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

There is an algorithm faster than O(N*M). Suppose that the sequences are A and B. For each element that occurs in A write its positions in B in decreasing order.

For the given case:

5 6

1 2 3 4 1

3 4 1 2 1 3

It should look like this:

1 -> (5,3)

2 -> (4)

3 -> (6,1)

4 -> (2)

Then replace each element in A with its list:

(5,3) (4) (6,1) (2) (5,3)

5 3 4 6 1 2 5 3

Find one of its longest increasing subsequences X(There are a lot of algorithms for doing this fast like binary search, fenwick tree, segment tree and so on).

Then just print B[X1], B[X2], ..., B[Xk].

For example we can take 3, 4 and 6 as an increasing subsequence. Then we just print B[3]=1, B[4]=2 and B[6]=1 which is a valid answer.

Edit: It's not faster every time. If there is a case where all numbers in the sequences are the same it will be slower. But it's good with random test cases. When you make the list for each number you can check which of the algorithms is better to use.

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

    You're wrong. Your algorithm fails on a very simple test:

    2
1 1
2
1 1

    Furthermore, it is believed (or even proved, I'm not sure) that general LCS problem cannot be solved in o(NM).

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

      Why do you think that it fails? The list for 1 is (2,1) and the sequence is 2 1 2 1. Its longest increasing subsequence is of length 2 -> 1 2. And the answer is B[1], B[2] -> 1 1. It's not wrong.

      Note: We are to find a LCS of two sequences :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yep, sure, it should be LCS :)

        Yes, you're right, your algorithm passes this test, it was my misunderstanding.

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

There is an algo working in O(500·(N + M)). Here is the idea.

The standard DP for this problem is d[i][j] = k = LCS of S[0..i] and T[0..j]. Let's swap the parameter and the value: g[i][k] = minimal j that LCS of S[0..i] and T[0..j] = k.

Then, g[i][k] = min(g[i-1][k], nextOcc[s[i]][g[i-1][k-1]]), where nextOcc[c][j] is the position of the first occurrence of c in T after position j.

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

    What is LIS in your text? We have to find LCS — longest common subsequence. How to calculate g[i][k] faster than n^2? What is 500?

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

      In this case k is 500. If you replace LIS with LCS in his text it should be valid. The transition state is also O(1), since g[i][k] only requires g[i-1][k] and g[i-1][k-1]. The definition of g[i][k] is just as stated above, just make sure you recognize which variables correspond to which.

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

      It's a typo, LIS should be read as LCS (never write anything late at night).

      The second parameter is a bound for the answer (500 in this exact problem).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        I have not seen this constraint beacause it was in section "output format". And problem statement still unclear "Print the longest common subsequence, with length no greater than 500". What if length of actual LCS is greater than 500? can I print any common subsquence with length 500, or only subsequence of actual LCS?

        → Reply