## Number of Distinct LCS

This problem appeared in the November edition of CodeChef Monthly Contest. The problem is to find the number of distinct LCS that can be formed from the given two strings. A nice tutorial about it is given on the CodeChef site itself. Also there is a research paper available here. Here’s my solution to the CodeChef problem.

#include<iostream> using namespace std; int L[1005][1005]; int D[1005][1005]; int LCS(string X,string Y) { int m = X.length(),n=Y.length(); int i,j; for (i=0;i<=m;i++) { for (j=0;j<=n;j++) { if (i==0 || j==0) L[i][j]=0; else { if (X[i-1]==Y[j-1]) L[i][j]=L[i-1][j-1]+1; else L[i][j]=max(L[i][j-1],L[i-1][j]); } } } return (L[m][n]); } int NLCS(string X,string Y) { int m = X.length(),n=Y.length(); int i,j; for (i=0;i<=m;i++) { for (j=0;j<=n;j++) { if (i==0 || j==0) D[i][j]=1; else { D[i][j]=0; if (X[i-1]==Y[j-1]) { D[i][j]=D[i-1][j-1]; } else { if (L[i-1][j]==L[i][j]) D[i][j]=(D[i][j]+D[i-1][j])%23102009; if (L[i][j-1]==L[i][j]) D[i][j]=(D[i][j]+D[i][j-1])%23102009; if (L[i-1][j-1]==L[i][j]) { if (D[i][j]<D[i-1][j-1]) D[i][j]+=23102009; D[i][j]=(D[i][j]-D[i-1][j-1]); } } } } } return (D[m][n]); } int main() { string X,Y; int T,A,B; scanf("%d",&T); while (T--) { cin>>X>>Y; A=LCS(X,Y); B=NLCS(X,Y); printf("%d %d\n",A,B); } }

NJOY!

-fR0DDY

Advertisements

cn u tell me in this how to print all the sequences??

ishanApril 18, 2010 at 4:03 AM

Could you plz explain me the part NLCS() with giving an example.. it will be helpful for me..

HalderSeptember 23, 2013 at 2:49 PM