rajon_aust's blog

By rajon_aust, history, 9 years ago, In English

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" ) .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rajon_aust (previous revision, new revision, compare).

»
9 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

26 * (N ^ 2) * needLength solution.

dp[i][j][len] — count of subsequences with length len and last symbol we took in seq A was sym at pos i, last sym we took in seq B was sym at pos j.

Update other state: lets fix symbol C. find leftmost position pos such that pos > i && a[pos] == C, find leftmost position pos2 such that pos2 > j && b[pos2] == C, update state (pos, pos2, len + 1);

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rajon_aust (previous revision, new revision, compare).