Largest common subsequence algorithm

/*
* Status: Tested OK
* Title: Largest common subsequence algorithm
* Category: String matching
* Difficulty Level: High
* Name: Akshay Thakare
*/

/*
Functions involved
1. lcs_calc
2. lcs_print
*/

/*
Debug procedure
1. main
2. lcs_calc
3. lcs_print
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Global Variables*/
char * s1;					//To store string 1
char * s2;					//To store string 2
int m,n;					//To store the calculated length of both strings
int ** sol;
char  ** dir;

/*Prototype*/
void lcs_calc();
void lcs_print();

/*Start of the program*/

int main()
{
	int i,j;
	
	/*Take input of length of string from user*/
	printf("\nEnter the length of string 1 = ");
	scanf("%d",&n);
	printf("\nEnter the length of string 2 = ");
	scanf("%d",&m);
	
	/*String memory allocation*/
	s1 = (char *)malloc(n*sizeof(char));
	s2 = (char *)malloc(m*sizeof(char));
	
	/*Take string from user*/
	printf("\nEnter the string 1 = ");
	scanf("%s",s1);
	printf("\nEnter the string 2 = ");
	scanf("%s",s2);

	/*Solution array memory allocation*/			//IMP
	
	m++;			//IMP
	n++;			//IMP
	
	sol = malloc(n * sizeof(int *));
	for(i = 0; i < n; i++)
	{
		sol[i] = malloc(m * sizeof(int));
	}
		
	dir = malloc(n * sizeof(char *));
	for(i = 0; i < n; i++)
	{
		dir[i] = malloc(m * sizeof(char));
	}
	
	m--;			//IMP
	n--;			//IMP
	
	for(i=0;i!=n;i++)
		for(j=0;j!=m;j++)
			sol[i][j]=0;

	//n->down m->right
	
	lcs_calc();
	lcs_print();
	
	return 0;
}

void lcs_calc()
{
	int i,j;
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				sol[i][j]=sol[i-1][j-1]+1;
				dir[i][j]='D';
			}
			else 
			{
				if(sol[i-1][j]>sol[i][j-1])
				{
					sol[i][j]=sol[i-1][j];
					dir[i][j]='U';
				}
				else
				{
					sol[i][j]=sol[i][j-1];
					dir[i][j]='L';
				}
			}
		}
	}
}

void lcs_print()
{
	int i=n,j=m;
	
	while(j!=0)
	{
		if(dir[i][j]=='D')
		{
			printf("%c",s1[i-1]);			//IMP
			j--;
			i--;
		}
		if(dir[i][j]=='U')
		{
			i--;
		}
		if(dir[i][j]=='L')
		{
			j--;
		}
	}
}

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