Longest Common Subsequence

Правка en3, от 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" ) .

Теги lcs, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский rajon_aust 2015-08-15 15:00:24 2 Tiny change: ' and B is 1 . So numb' -> ' and B is 4 . So numb'
en2 Английский rajon_aust 2015-08-15 14:12:29 7 Tiny change: ' distinct sub-seque' -> ' distinct common sub-seque'
en1 Английский rajon_aust 2015-08-15 14:09:18 531 Initial revision (published)