shubhamchandra's blog

By shubhamchandra, history, 7 years ago, In English

It falls under dynamic programming tag. Around 180 people have done this. I don't know if its an easy problem or a very difficult problem. There's not much editorial available online. The problem asks to find the no. of distinct common subsequences b/w four given strings. ex: aaaa ,aaaa , aaaa ,aaaa No. of distinct common subsequences b/w them are 4. i.e, a, aa, aaa , aaaa let the strings be s1,s2,s3,s4. let T(w,x,y,z) calculate the no. of distinct subsequences b/w s1[1..w] , s2[1..x] , s3[1..y] , s4[1..z] what will be the recurence relation when s1[w] == s2[x] == s3[y] == s4[z] (its not 1 + 2*T(w — 1,x — 1,y — 1,z — 1) coz in the above example T(3,3,3,3) = 3 , T(4,4,4,4) = 4 != 1 + 2*3) and otherwise.

Plz help!!

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it