What is the best way to find LCS?

Revision en1, by wonderful_trip, 2021-01-30 10:55:07

I just know how to find LCS use dynamic programming:

if (s1 [i] == s2 [i]) 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!!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English wonderful_trip 2021-01-30 10:55:45 2 Tiny change: 'i] == s2 [i])\ndp [i]' -> 'i] == s2 [j])\ndp [i]'
en1 English wonderful_trip 2021-01-30 10:55:07 325 Initial revision (published)