wonderful_trip's blog

What is the best way to find LCS?
By wonderful_trip, history, 4 years ago, In English

I just know how to find LCS use dynamic programming:

if (s1 [i] == s2 [j]) dp [i] [j] = dp [i-1] [j-1] +1; else dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]).

But I have trouble with problem: Find LCS with s1 <= 1e6 and s2 > 1e3. What is the best way to find LCS? Thanks for help!!!

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

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

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

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

there is some algorithm that uses less time and memory but it is very uncomfortable to use.

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

Source of the problem?

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

    http://cnpt.edu.vn/problem/dplcs12 This is a link of problem.

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

      If one of the strings is small, then the answer must also be small. In this case, let's try to swap the dimensions of our dp around. Try fixing the prefix of the smaller string and the length of the answer.

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

I think a solution using bit operations will work.

→ Reply