How can we solve this problem? — http://www.spoj.com/problems/CSUBSEQS/

Revision en2, by shubhamchandra, 2017-04-30 20:06:21

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

Tags dynamic programming, spoj problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shubhamchandra 2017-04-30 20:06:21 575
en1 English shubhamchandra 2017-04-27 19:24:48 267 Initial revision (published)