What is the best way to find LCS?
Difference between en1 and en2, changed 2 character(s)
I just know how to find LCS use dynamic programming:↵
↵
if (s1 [i] == s2 [ij])↵
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)