Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Abinash's blog

By Abinash, 6 years ago, , You are developing a 'Love calculator'. So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things: 1.The length of the shortest string that contains the names as subsequence. 2.Total number of unique shortest strings which contain the names as subsequence. Now your task is to find these parts.

I find 1st part by computing (length of 1st name +length of 2nd name — LCS(1st name , 2nd name ).

But how to find 2nd part ?? lcs, Comments (8)
 » We know unique string length from s1.length+s2.length — LCS(s1,s2)=L. Lets define the DP states , one states will be unique string length (L) , another two will be s1.length(a) and s2.length(b). The recurrence will be ... 1.We take a letter from first string means solve(l-1,a-1,b). 2. We take a letter from second string means solve(l-1,a,b-1). 3. If letter from first string and second string same that means solve(l-1,a-1,b-1) cause if we take from both string will not unique. Now come some condition... 1. If letter from first string and second string same that means , we have only one way . solve(l-1,a-1,b-1). 2. If letter from first string and second string different that means we have two way solve(l-1,a-1,b) and solve(l-1,a,b-1) . 3. If any a=0 then we must have take letter from second string means solve(l-1,a,b-1) . 4. If any b=0 then we must have take letter from first string means solve(l-1,a-1,b).
•  » » int solve(int l,int a,int b) {  if(l==0) return 1; if(dp[l][a][b]!=-1) return dp[l][a][b]; if(a==0) return dp[l][a][b]=solve(l-1,a,b-1); if(b==0) return dp[l][a][b]=solve(l-1,a-1,b); if(s1[a-1]==s2[b-1]) return dp[l][a][b]=solve(l-1,a-1,b-1); return dp[l][a][b]=(solve(l-1,a,b-1)+solve(l-1,a-1,b)); }int not understanding why my implementation is not working for the sample test case
 » N is the length of the first string and M is the length of the second string. void Compute_Ways() { lli i,j; rep(i,0,N+1) { Ways[i]=1; } rep(i,0,M+1) { Ways[i]=1; } rep(i,1,N+1) { rep(j,1,M+1) { if(s[i-1]==s1[j-1]) { Ways[i][j]=Ways[i-1][j-1]; } else { if(LCS[i-1][j]==LCS[i][j-1]) { Ways[i][j]=Ways[i-1][j]+Ways[i][j-1]; } else { if(LCS[i-1][j]>LCS[i][j-1]) Ways[i][j]=Ways[i-1][j]; else Ways[i][j]=Ways[i][j-1]; } } } }}
•  » » Could you please explain briefly why do we use the LCS to find ways?