Longest Common Subsequence

A. First Edition
This is just a simple practice of algorithms of Longest Common Subsequence. 
B.The problem

How to find the longest common subsequence? Here the common subsequence is defined to be common string such that

you can omit one or more character within the string. i.e. "string" and "satirainsg" have the common subsequence

of "string" even the second string has so many garbage within it. You just ignore them and continue to move

your cursor.

What I am doing here is try to test my idea that I can compare and get the longest common subsequence among

THREE strings by comparing the result common subsequence of two with the third string.

C.The idea of program
กก

This is the standard algorithm from textbook. The only thing I misunderstand is that when you re-construct the

common string from the matrix, you need to add the character into your stack unless it is surely not from

"different" case. (Do you understand? See the algorithm and you know that it will write down the max of its

neighbour if the two character from two string are different. If same, you write down the upper-left number plus

one.)

D.The major functions
กก
E.Further improvement
กก
F.File listing
1. LCS.h
2. LCS.cpp
3. main.cpp
file name: LCS.h
class LCS
{
private:
	int** matrix;
	char* rowStr;
	char* colStr;
	int row, col;
	int curRow, curCol;
	void initialize(char* str1, char* str2);
	void diffCase(int r, int c);
	void sameCase(int r, int c);
	void printMatrix();
	void uninitialize();
public:
	char* stack;
	int compStr(const char* str1, const char* str2);
	void print();
	LCS();
	~LCS();
};
file name: LCS.cpp
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "LCS.H"

LCS::~LCS()
{
	uninitialize();
}

void LCS::uninitialize()
{
	if (matrix!=NULL)
	{
		for (int i=0; i<row; i++)
		{
			delete [] matrix[i];
		}
		delete [] matrix;
		matrix=NULL;
	}
	if (stack!=NULL)
	{
		delete [] stack;
	}
	stack=NULL;
}

LCS::LCS()
{
	matrix=NULL;
	rowStr=colStr=stack=NULL;
	curRow=curCol=0;
}


void LCS::initialize(char* str1, char* str2)
{
	uninitialize();
	row=strlen(str1);
	col=strlen(str2);
	rowStr=(char*)str1;
	colStr=(char*)str2;
	matrix=new int*[row];
	for (int i=0; i<row; i++)
	{
		matrix[i]=new int[col];
		for (int j=0; j<col; j++)
		{
			//because every row by default has maximum of this number
			matrix[i][j]=i+1;
		}
	}
}

int LCS::compStr(const char* str1, const char* str2)
{
	initialize((char*)str1, (char*)str2);
	for (int r=0; r<row; r++)
	{
		for (int c=0; c<col; c++)
		{
			if (str1[r]!=str2[c])
			{
				diffCase(r, c);				
			}
			else
			{
				sameCase(r, c);
			}
			//if exceeds the limit, no need for further 
			if (matrix[r][c]==r+1)
			{
				break;
			}
		}
	}
	return matrix[row-1][col-1];
}

void LCS::printMatrix()
{
	for (int r=0; r<col; r++)
	{
		printf("%2d  ", r+1);
	}
	printf("\n");
	for ( r=0; r<row; r++)
	{
		for (int c=0; c<col; c++)
		{
			printf("%2d  ", matrix[r][c]);
		}
		printf("\n");
	}
}


void LCS::print()
{
	int r=row-1, c=col-1, len=matrix[row-1][col-1];
	stack=new char[len+1];
	stack[len]='\0';
	printMatrix();
	printf("str1=%s\nstr2=%s\n", rowStr, colStr);
	while (r!=0&&c!=0)
	{
		if (matrix[r][c]==matrix[r-1][c])
		{			
			r--;			
		}
		else
		{
			if (matrix[r][c]==matrix[r][c-1])
			{
				c--;
			}
			else
			{
				//it must be same for the last one
				stack[--len]=rowStr[r];
				r--;
				c--;
			}
		}
	}
	if (len>0)
	{
		stack[--len]=rowStr[r];
	}
	printf("the common subsequence is:%s\n", stack);
}

void LCS::sameCase(int r, int c)
{
	if (r!=0&&c!=0)
	{
		matrix[r][c]=matrix[r-1][c-1]+1;
	}
	else
	{
		matrix[r][c]=1;
	}
}

void LCS::diffCase(int r, int c)
{
	if (r!=0&&c!=0)
	{
		if (matrix[r][c-1]>matrix[r-1][c])
		{
			matrix[r][c]=matrix[r][c-1];
		}
		else
		{
			matrix[r][c]=matrix[r-1][c];
		}
	}
	else
	{
		matrix[r][c]=0;
	}
}


file name: main.cpp
#include "LCS.H"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



char* str1="010010100100111100";
char* str2="10001111010010101001001";
char* str3="01010010100101101";

int main()
{
	char buffer[30];
	LCS L;
	printf("The length is %d\n", L.compStr(str1, str2));
	L.print();
	strcpy(buffer, L.stack);
	printf("The length is %d\n", L.compStr(buffer, str3));
	L.print();
	printf("The length is %d\n", L.compStr(str1, str3));
	L.print();
	strcpy(buffer, L.stack);
	printf("The length is %d\n", L.compStr(buffer, str2));
	L.print();

	printf("The length is %d\n", L.compStr(str2, str3));
	L.print();
	strcpy(buffer, L.stack);
	printf("The length is %d\n", L.compStr(buffer, str1));
	L.print();


	return 0;
}








How to run?
I try to get the longest common subsequence from THREE strings. First, I compare two strings and get the result 
of LCS. Then I use the result to compare with the third because the common subsequence must be subsequence of
the longest common subsequence from previous two strings. Can you test it for me?
 
1. The following I am just comparing str1 and str2. Then I compare the result with str3.
2. Secondly I change the comparing sequence: I compare str1 with str3. Then compare the result with str2.
3. Thirdly I change the sequence again. str2 and str3 first and then result with str1.
4. The results of 1) and 2) are different. And result of 1) and 3) are same.
The length is 15
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
 0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1   1   1   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 0   2   2   2   2   2   2   2   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3
 0   1   3   3   3   3   3   3   3   3   4   4   4   4   4   4   4   4   4   4   4   4   4
 1   1   3   3   4   4   4   4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5
 0   2   2   4   4   4   4   4   5   5   5   5   5   6   6   6   6   6   6   6   6   6   6
 1   2   2   4   5   5   5   5   5   6   6   6   6   6   7   7   7   7   7   7   7   7   7
 0   2   3   3   5   5   5   5   6   6   7   7   7   7   7   8   8   8   8   8   8   8   8
 0   1   3   4   5   5   5   5   6   6   7   8   8   8   8   8   8   9   9   9   9   9   9
 1   1   3   4   5   6   6   6   6   7   7   8   9   9   9   9   9   9   9  10  10  10  10
 0   2   2   4   5   6   6   6   7   7   8   8   9  10  10  10  10  10  10  10  11  11  11
 0   1   3   3   5   6   6   6   7   7   8   9   9  10  10  11  11  11  11  11  11  12  12
 1   1   3   3   4   6   7   7   7   8   8   9  10  10  11  11  12  12  12  12  12  12  13
 1   1   3   3   4   5   7   8   8   8   8   9  10  10  11  11  12  12  12  13  13  13  13
 1   1   3   3   4   5   6   8   8   9   9   9  10  10  11  11  12  12  12  13  13  13  14
 1   1   3   3   4   5   6   7   8   9   9   9  10  10  11  11  12  12  12  13  13  13  14
 0   2   2   4   4   5   6   7   8   9  10  10  10  11  11  12  12  13  13  13  14  14  14
 0   1   3   3   4   5   6   7   8   9  10  11  11  11  11  12  12  13  14  14  14  15  15
str1=010010100100111100
str2=10001111010010101001001
the common subsequence is:100101001001100
The length is 13
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
 0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 1   1   2   2   3   3   3   3   3   3   3   3   3   3   3   3   3
 0   2   2   3   3   3   4   4   4   4   4   4   4   4   4   4   4
 1   2   3   3   4   4   4   5   5   5   5   5   5   5   5   5   5
 0   2   3   4   4   4   5   5   6   6   6   6   6   6   6   6   6
 1   2   3   4   5   5   5   6   6   7   7   7   7   7   7   7   7
 1   2   3   4   5   6   6   6   6   7   8   8   8   8   8   8   8
 0   2   3   4   5   6   7   7   7   7   8   9   9   9   9   9   9
 1   2   3   4   5   6   7   8   8   8   8   9  10  10  10  10  10
 1   2   3   4   5   6   7   8   8   9   9   9  10  10  10  11  11
 0   2   3   4   5   6   7   8   9   9   9  10  10  11  11  11  12
 0   1   3   4   5   6   7   8   9   9   9  10  10  11  12  12  12
 1   1   2   4   5   6   7   8   9  10  10  10  11  11  12  13  13
 1   1   2   4   5   6   7   8   9  10  11  11  11  11  12  13  13
str1=100101001001100
str2=01010010100101101
the common subsequence is:1001010010110
The length is 14
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 0   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 1   2   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3
 1   2   3   3   4   4   4   4   4   4   4   4   4   4   4   4   4
 0   2   3   4   4   4   5   5   5   5   5   5   5   5   5   5   5
 1   2   3   4   5   5   5   6   6   6   6   6   6   6   6   6   6
 0   2   3   4   5   5   6   6   7   7   7   7   7   7   7   7   7
 1   2   3   4   5   6   6   7   7   8   8   8   8   8   8   8   8
 1   2   3   4   5   6   6   7   7   8   9   9   9   9   9   9   9
 0   2   3   4   5   6   7   7   8   8   9  10  10  10  10  10  10
 1   2   3   4   5   6   7   8   8   9   9  10  11  11  11  11  11
 1   2   3   4   5   6   7   8   8   9  10  10  11  11  11  12  12
 0   2   3   4   5   6   7   8   9   9  10  11  11  12  12  12  13
 0   1   3   4   5   6   7   8   9   9  10  11  11  12  13  13  13
 0   1   3   4   5   6   7   8   9   9  10  11  11  12  13  13  14
 0   1   3   4   5   6   7   8   9   9  10  11  11  12  13  13  14
 1   1   2   4   5   6   7   8   9  10  10  11  12  12  13  14  14
 1   1   2   4   5   6   7   8   9  10  11  11  12  12  13  14  14
str1=010010100100111100
str2=01010010100101101
the common subsequence is:01001010010111
The length is 13
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
 0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1   1   1   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 0   2   2   2   2   2   2   2   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3
 0   1   3   3   3   3   3   3   3   3   4   4   4   4   4   4   4   4   4   4   4   4   4
 1   1   3   3   4   4   4   4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5
 0   2   2   4   4   4   4   4   5   5   5   5   5   6   6   6   6   6   6   6   6   6   6
 1   2   2   4   5   5   5   5   5   6   6   6   6   6   7   7   7   7   7   7   7   7   7
 0   2   3   3   5   5   5   5   6   6   7   7   7   7   7   8   8   8   8   8   8   8   8
 0   1   3   4   5   5   5   5   6   6   7   8   8   8   8   8   8   9   9   9   9   9   9
 1   1   3   4   5   6   6   6   6   7   7   8   9   9   9   9   9   9   9  10  10  10  10
 0   2   2   4   5   6   6   6   7   7   8   8   9  10  10  10  10  10  10  10  11  11  11
 1   2   2   4   5   6   7   7   7   8   8   8   9  10  11  11  11  11  11  11  11  11  12
 1   2   2   4   5   6   7   8   8   8   8   8   9  10  11  11  12  12  12  12  12  12  12
 1   2   2   4   5   6   7   8   8   9   9   9   9  10  11  11  12  12  12  13  13  13  13
str1=01001010010111
str2=10001111010010101001001
the common subsequence is:1001010010111
The length is 15
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
 0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 1   1   2   2   3   3   3   3   3   3   3   3   3   3   3   3   3
 1   1   2   2   3   4   4   4   4   4   4   4   4   4   4   4   4
 0   2   2   3   3   4   5   5   5   5   5   5   5   5   5   5   5
 0   1   2   3   3   4   5   5   6   6   6   6   6   6   6   6   6
 0   1   2   3   3   4   5   5   6   6   6   7   7   7   7   7   7
 0   1   2   3   3   4   5   5   6   6   6   7   7   8   8   8   8
 1   1   2   3   4   4   5   6   6   7   7   7   8   8   8   9   9
 0   2   2   3   4   4   5   6   7   7   7   8   8   9   9   9  10
 1   2   3   3   4   5   5   6   7   8   8   8   9   9   9  10  10
 1   2   3   3   4   5   5   6   7   8   9   9   9   9   9  10  10
 0   2   3   4   4   5   6   6   7   8   9  10  10  10  10  10  11
 1   2   3   4   5   5   6   7   7   8   9  10  11  11  11  11  11
 0   2   3   4   5   5   6   7   8   8   9  10  11  12  12  12  12
 1   2   3   4   5   6   6   7   8   9   9  10  11  12  12  13  13
 0   2   3   4   5   6   7   7   8   9   9  10  11  12  13  13  14
 1   2   3   4   5   6   7   8   8   9  10  10  11  12  13  14  14
 1   2   3   4   5   6   7   8   8   9  10  10  11  12  13  14  14
 0   2   3   4   5   6   7   8   9   9  10  11  11  12  13  14  15
 1   2   3   4   5   6   7   8   9  10  10  11  12  12  13  14  15
 1   2   3   4   5   6   7   8   9  10  11  11  12  12  13  14  15
 0   2   3   4   5   6   7   8   9  10  11  12  12  13  13  14  15
str1=10001111010010101001001
str2=01010010100101101
the common subsequence is:100010100101101
The length is 13
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18
 0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 1   1   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2
 1   1   2   3   3   3   3   3   3   3   3   3   3   3   3   3   3   3
 1   1   2   3   3   4   4   4   4   4   4   4   4   4   4   4   4   4
 0   2   2   3   4   4   5   5   5   5   5   5   5   5   5   5   5   5
 1   2   3   3   4   5   5   6   6   6   6   6   6   6   6   6   6   6
 0   2   3   3   4   5   6   6   6   7   7   7   7   7   7   7   7   7
 1   2   3   4   4   5   6   7   7   7   8   8   8   8   8   8   8   8
 1   2   3   4   4   5   6   7   8   8   8   9   9   9   9   9   9   9
 0   2   3   4   5   5   6   7   8   9   9   9  10  10  10  10  10  10
 1   2   3   4   5   6   6   7   8   9  10  10  10  10  10  10  11  11
 0   2   3   4   5   6   7   7   8   9  10  10  11  11  11  11  11  11
 0   1   3   4   5   6   7   7   8   9  10  10  11  12  12  12  12  12
 1   1   2   4   5   6   7   8   8   9  10  11  11  12  12  12  13  13
 0   2   2   4   5   6   7   8   8   9  10  11  12  12  13  13  13  13
str1=100010100101101
str2=010010100100111100
the common subsequence is:1001010010110
Press any key to continue




                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)