Longest Common Subsequence

Revision en3, by rajon_aust, 2015-08-15 15:00:24

Today I solved the problem . Link : http://lightoj.com/volume_showproblem.php?problem=1157

I have a question . If the problem is modified and say to find the number of distinct common sub-sequences of n ( 0<=n<=1000 ) length than is it possible to come up a solution ?

let A = "abba" ans B = "abba" , here LCS between A and B is 4 . So number of distinct LCS between A and B is 1 . But if said find the number of distinct common sub-sequences of 3 length than answer will be 3 ( "abb" , "aba" , "bba" ) .

Tags lcs, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rajon_aust 2015-08-15 15:00:24 2 Tiny change: ' and B is 1 . So numb' -> ' and B is 4 . So numb'
en2 English rajon_aust 2015-08-15 14:12:29 7 Tiny change: ' distinct sub-seque' -> ' distinct common sub-seque'
en1 English rajon_aust 2015-08-15 14:09:18 531 Initial revision (published)