COME ON CODE ON

A blog about programming and more programming.

Number of Distinct LCS

with 2 comments

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

Written by fR0DDY

November 13, 2009 at 1:06 PM

Posted in Programming

Tagged with , , , , , ,

2 Responses

Subscribe to comments with RSS.

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

    ishan

    April 18, 2010 at 4:03 AM

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

    Halder

    September 23, 2013 at 2:49 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: