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