What is the best way to find LCS?

Правка en2, от wonderful_trip, 2021-01-30 10:55:45

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!!!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский wonderful_trip 2021-01-30 10:55:45 2 Tiny change: 'i] == s2 [i])\ndp [i]' -> 'i] == s2 [j])\ndp [i]'
en1 Английский wonderful_trip 2021-01-30 10:55:07 325 Initial revision (published)