jugal_sahu's blog

ADFRUITS — Advanced Fruits
By jugal_sahu, 10 years ago, In English

I was trying to solve this problem . I even searched for solution but was unable to understand .Can any one explain how to solve it.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem statement: http://www.spoj.com/problems/ADFRUITS/

The thing that you are looking for is called shortest common supersequence(or just SCS).

The length of SCS(a,b) and be computed using simple DP:

Let dp[i][j] is the length of the shortest common supersequence of a[1],...,a[i] and b[1],...,b[j].

Then there are two cases:

1) If a[i]=b[j], then dp[i][j]=1+dp[i-1][j-1].

2) If a[i]!=b[j], then dp[i][j]=1+min(dp[i-1][j],dp[i][j-1]).

Now, think how to restore the SCS after computing the dp array.

→ Reply