Longest Common Subsequence(experiment)

A. Second Edition
I am using the LCS to do a series meaningless little experiments. 
B.The problem

1. How to find common sub-sequence among strings of more than two?

2. What is the relationship between common sub-sequence and its parental sequences? If represented by decimal

integer, can you recognize the fathers from their son?

C.The idea of program
กก

1. How to find common sub-sequence among strings of more than two?

I started with three strings and it turned out to be meaningless since different sequences lead to different

results. I then tried to increase the number of sequences to five. Then I need a little "permutation-generator"

to generate all permutation of sequences. Here I used the recursive function "permute" which needs a function

pointer which will use that sequences generated by "permute" function. It sounds a bit bizarre, but I cannot

find a better solution since I hate to ask user to make repeated calls to permute unless it return some stopping

signal (i.e. strtok?).

2. What is the relationship between common sub-sequence and its parental sequences? If represented by decimal

integer, can you recognize the fathers from their son?

This is like a little joke because how come there is any relationship between decimal and binary representation

of sequences of "0" and "1". However, it is a little surprise for me to try to change binary into decimal.

Frankly speaking, I tried more than a couple ways. It is too easy, uh? Still you need to do it to discover

something you haven't imagined.

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(bool showMatrix=false);
	LCS();
	bool isSubstr(char* father, char* son);
	~LCS();
};
กก
file name: LCS.cpp
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "LCS.H"


bool LCS::isSubstr(char* father, char* son)
{
	char* pFather=father, * pSon=son;
	while (*pSon!='\0')
	{
		if (*pFather=='\0')
		{
			return false;
		}
		if (*pFather==*pSon)
		{
			pFather++;
			pSon++;
		}
		else
		{
			pFather++;
		}
	}
	return true;
}

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(bool showMatrix)
{
	int r=row-1, c=col-1, len=matrix[row-1][col-1];
	stack=new char[len+1];
	stack[len]='\0';
	if (showMatrix)
	{
		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>
#include <time.h>

const int MaxStringLength=10;
const int MaxStringNumbers=5;
/*
char* str1="010010100100111100";
char* str2="10001111010010101001001";
char* str3="010100101001011010";

char* str1="010010100";
char* str2="1000111101";
char* str3="010101101";
*/

char strings[MaxStringNumbers][MaxStringLength+1];

void genStr();
void permute(int num1, int num2, int num3);
int binary(char* str);

LCS L;

int sequence[MaxStringNumbers];

void permute(int index, void (*user)(int seq[]));

void compThree();
void compTwo(int seq[]);


int main()
{
	srand(time(0));
	for (int i=0; i<MaxStringNumbers; i++)
	{
		sequence[i]=i;
	}
	genStr();

	compTwo(sequence);

	permute(0, compTwo);
	//printf("%d\n", binary("011001"));

/*
	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));
	printf("str1^str2^str3:\n");
	L.print();
	printf("\n");
	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));
	printf("str1^str3^str2:\n");
	L.print();
	printf("\n");
	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));
	printf("str2^str3^str1:\n");
	L.print();
	printf("\n");
*/
	return 0;
}

int binary(char* str)
{
	char* ptr=str;
	int result=0;
	while (true)
	{
		if (*ptr=='1')
		{
			result+=1;
		}
		ptr++;
		if (*ptr=='\0')
		{
			break;
		}
		result=result<<1;
	}
		

	return result;
}

void swap(int i, int j)
{
	int temp;
	temp=sequence[i];
	sequence[i]=sequence[j];
	sequence[j]=temp;
}

void permute(int index,  void (*user)(int seq[]))
{
	void swap(int i, int j);

	if (index==MaxStringNumbers-1)
	{
		return;
	}

	for (int i=index+1; i<MaxStringNumbers; i++)
	{
			swap(i, index);
			user(sequence);
			permute(index+1, user);
			swap(i, index);//back
	
	}
}






void compTwo(int seq[])
{
	char buffer[MaxStringLength+1];
	strcpy(buffer, strings[seq[0]]);
	for (int i=1; i<MaxStringNumbers; i++)
	{
		printf("The length is %d\n", L.compStr(buffer, strings[seq[i]]));
		L.print();
		strcpy(buffer, L.stack);
		//printf("str1=%d\nstr2=%d\nsubstr=%d\n", binary(strings[seq[i]]), binary(strings[seq[i+1]]),
		//binary(L.stack));
	}
	printf("the sequence is:\n");
	for (i=0; i<MaxStringNumbers; i++)
	{
		printf("seq[%d]=%d;", i, seq[i]);
	}
	printf("\n");
}

void compThree()
{
	genStr();
	permute(0,1,2);
	permute(1,2,0);
	permute(2,0,1);
}


void permute(int num1, int num2, int num3)
{
	char buffer[30];
	
	printf("sequence of %d-->%d-->%d\n", num1, num2, num3);
	printf("The length is %d\n", L.compStr(strings[num1], strings[num2]));
	L.print();
	strcpy(buffer, L.stack);
	printf("The length is %d\n", L.compStr(buffer, strings[num3]));
	L.print();

	if (!L.isSubstr(strings[num1], L.stack))
	{
		printf("%s is not common substring of str%d\n", L.stack, num1);
	}
	if (!L.isSubstr(strings[num2], L.stack))
	{
		printf("%s is not common substring of str%d\n", L.stack, num2);
	}

	if (!L.isSubstr(strings[num3], L.stack))
	{
		printf("%s is not common substring of str%d\n", L.stack, num3);
	}
}


void genStr()
{
	int len;
	int scale=3;
	for (int i=0; i<MaxStringNumbers; i++)
	{
		len=rand()%scale+MaxStringLength-scale;//not empty
		for (int j=0; j<len; j++)
		{
			strings[i][j]=rand()%2?'0':'1';
		}
		strings[i][j]='\0';
	}
	for (i=0; i<MaxStringNumbers; i++)
	{
		printf("str%d:%s\n", i, strings[i]);
	}
}
How to run?
I try to get the longest common subsequence from FIVE strings by trying all their permutation of sequence.
 
1. The sequences gives you the sequence of index of strings for comparing strings.
2. Secondly I copy the result common sequence to a buffer and compare with next string which index is in next of "sequence" array.
3. Go on and on.
4. Try next sequence which is another permutation of sequence of strings. 
5. The result is not necessarily same. And I fail to find a clue for algorithm of finding LCS among multi-sequences.
str0:010111001
str1:01010000
str2:110000011
str3:0110111
str4:000110001
The length is 6
str1=010111001
str2=01010000
the common subsequence is:010100
The length is 4
str1=010100
str2=110000011
the common subsequence is:1000
The length is 2
str1=1000
str2=0110111
the common subsequence is:10
The length is 2
str1=10
str2=000110001
the common subsequence is:10
the sequence is:
seq[0]=0;seq[1]=1;seq[2]=2;seq[3]=3;seq[4]=4;
The length is 6
str1=01010000
str2=010111001
the common subsequence is:010100
The length is 4
str1=010100
str2=110000011
the common subsequence is:1000
The length is 2
str1=1000
str2=0110111
the common subsequence is:10
The length is 2
str1=10
str2=000110001
the common subsequence is:10
the sequence is:
seq[0]=1;seq[1]=0;seq[2]=2;seq[3]=3;seq[4]=4;
The length is 6
str1=01010000
str2=110000011
the common subsequence is:100000
The length is 4
str1=100000
str2=010111001
the common subsequence is:1000
The length is 2
str1=1000
str2=0110111
the common subsequence is:10
The length is 2
str1=10
str2=000110001
the common subsequence is:10
the sequence is:
seq[0]=1;seq[1]=2;seq[2]=0;seq[3]=3;seq[4]=4;
The length is 6
str1=01010000
str2=110000011
the common subsequence is:100000
The length is 2
str1=100000
str2=0110111
the common subsequence is:10
The length is 2
str1=10
str2=010111001
the common subsequence is:10
The length is 2
str1=10
str2=000110001
the common subsequence is:10
the sequence is:
seq[0]=1;seq[1]=2;seq[2]=3;seq[3]=0;seq[4]=4;
The length is 6
str1=01010000
str2=110000011
the common subsequence is:100000
The length is 2
str1=100000
str2=0110111
the common subsequence is:10
The length is 2
str1=10
str2=000110001
the common subsequence is:10
The length is 2
str1=10
str2=010111001
the common subsequence is:10
the sequence is:
seq[0]=1;seq[1]=2;seq[2]=3;seq[3]=4;seq[4]=0;
The length is 6
str1=01010000
str2=110000011
the common subsequence is:100000
The length is 5
str1=100000
str2=000110001
the common subsequence is:00000
The length is 2
str1=00000
str2=0110111
the common subsequence is:00
The length is 2
str1=00
str2=010111001
the common subsequence is:00
the sequence is:
seq[0]=1;seq[1]=2;seq[2]=4;seq[3]=3;seq[4]=0;
The length is 6
str1=01010000
str2=110000011
the common subsequence is:100000
The length is 5
str1=100000
str2=000110001
the common subsequence is:00000
The length is 4
str1=00000
str2=010111001
the common subsequence is:0000
The length is 2
str1=0000
str2=0110111
the common subsequence is:00
the sequence is:
seq[0]=1;seq[1]=2;seq[2]=4;seq[3]=0;seq[4]=3;
The length is 4
str1=01010000
str2=0110111
the common subsequence is:0101
The length is 3
str1=0101
str2=110000011
the common subsequence is:101
The length is 3
str1=101
str2=010111001
the common subsequence is:101
The length is 3
str1=101
str2=000110001
the common subsequence is:101
the sequence is:
seq[0]=1;seq[1]=3;seq[2]=2;seq[3]=0;seq[4]=4;
The length is 4
str1=01010000
str2=0110111
the common subsequence is:0101
The length is 4
str1=0101
str2=010111001
the common subsequence is:0101
The length is 3
str1=0101
str2=110000011
the common subsequence is:101
The length is 3
str1=101
str2=000110001
the common subsequence is:101
the sequence is:
seq[0]=1;seq[1]=3;seq[2]=0;seq[3]=2;seq[4]=4;
The length is 4
str1=01010000
str2=0110111
the common subsequence is:0101
The length is 4
str1=0101
str2=010111001
the common subsequence is:0101
The length is 4
str1=0101
str2=000110001
the common subsequence is:0101
The length is 3
str1=0101
str2=110000011
the common subsequence is:101
the sequence is:
seq[0]=1;seq[1]=3;seq[2]=0;seq[3]=4;seq[4]=2;
The length is 4
str1=01010000
str2=0110111
the common subsequence is:0101
The length is 4
str1=0101
str2=000110001
the common subsequence is:0101
The length is 4
str1=0101
str2=010111001
the common subsequence is:0101
The length is 3
str1=0101
str2=110000011
the common subsequence is:101
the sequence is:
seq[0]=1;seq[1]=3;seq[2]=4;seq[3]=0;seq[4]=2;
The length is 4
str1=01010000
str2=0110111
the common subsequence is:0101
The length is 4
str1=0101
str2=000110001
the common subsequence is:0101
The length is 3
str1=0101
str2=110000011
the common subsequence is:101
The length is 3
str1=101
str2=010111001
the common subsequence is:101
the sequence is:
seq[0]=1;seq[1]=3;seq[2]=4;seq[3]=2;seq[4]=0;
The length is 6
str1=01010000
str2=000110001
the common subsequence is:001000
The length is 5
str1=001000
str2=110000011
the common subsequence is:00000
The length is 2
str1=00000
str2=0110111
the common subsequence is:00
The length is 2
str1=00
str2=010111001
the common subsequence is:00
the sequence is:
seq[0]=1;seq[1]=4;seq[2]=2;seq[3]=3;seq[4]=0;
The length is 6
str1=01010000
str2=000110001
the common subsequence is:001000
The length is 3
str1=001000
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=110000011
the common subsequence is:001
The length is 3
str1=001
str2=010111001
the common subsequence is:001
the sequence is:
seq[0]=1;seq[1]=4;seq[2]=3;seq[3]=2;seq[4]=0;
The length is 6
str1=01010000
str2=000110001
the common subsequence is:001000
The length is 3
str1=001000
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=010111001
the common subsequence is:001
The length is 3
str1=001
str2=110000011
the common subsequence is:001
the sequence is:
seq[0]=1;seq[1]=4;seq[2]=3;seq[3]=0;seq[4]=2;
The length is 6
str1=01010000
str2=000110001
the common subsequence is:001000
The length is 5
str1=001000
str2=010111001
the common subsequence is:00100
The length is 3
str1=00100
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=110000011
the common subsequence is:001
the sequence is:
seq[0]=1;seq[1]=4;seq[2]=0;seq[3]=3;seq[4]=2;
The length is 6
str1=01010000
str2=000110001
the common subsequence is:001000
The length is 5
str1=001000
str2=010111001
the common subsequence is:00100
The length is 4
str1=00100
str2=110000011
the common subsequence is:0000
The length is 2
str1=0000
str2=0110111
the common subsequence is:00
the sequence is:
seq[0]=1;seq[1]=4;seq[2]=0;seq[3]=2;seq[4]=3;
The length is 6
str1=110000011
str2=01010000
the common subsequence is:110000
The length is 4
str1=110000
str2=010111001
the common subsequence is:1100
The length is 3
str1=1100
str2=0110111
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=1;seq[2]=0;seq[3]=3;seq[4]=4;
The length is 5
str1=110000011
str2=010111001
the common subsequence is:11001
The length is 4
str1=11001
str2=01010000
the common subsequence is:1100
The length is 3
str1=1100
str2=0110111
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=0;seq[2]=1;seq[3]=3;seq[4]=4;
The length is 5
str1=110000011
str2=010111001
the common subsequence is:11001
The length is 4
str1=11001
str2=0110111
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=0;seq[2]=3;seq[3]=1;seq[4]=4;
The length is 5
str1=110000011
str2=010111001
the common subsequence is:11001
The length is 4
str1=11001
str2=0110111
the common subsequence is:1101
The length is 4
str1=1101
str2=000110001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=0;seq[2]=3;seq[3]=4;seq[4]=1;
The length is 5
str1=110000011
str2=010111001
the common subsequence is:11001
The length is 5
str1=11001
str2=000110001
the common subsequence is:11001
The length is 4
str1=11001
str2=0110111
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=0;seq[2]=4;seq[3]=3;seq[4]=1;
The length is 5
str1=110000011
str2=010111001
the common subsequence is:11001
The length is 5
str1=11001
str2=000110001
the common subsequence is:11001
The length is 4
str1=11001
str2=01010000
the common subsequence is:1100
The length is 3
str1=1100
str2=0110111
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=0;seq[2]=4;seq[3]=1;seq[4]=3;
The length is 5
str1=110000011
str2=0110111
the common subsequence is:11011
The length is 4
str1=11011
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=3;seq[2]=0;seq[3]=1;seq[4]=4;
The length is 5
str1=110000011
str2=0110111
the common subsequence is:11011
The length is 3
str1=11011
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=3;seq[2]=1;seq[3]=0;seq[4]=4;
The length is 5
str1=110000011
str2=0110111
the common subsequence is:11011
The length is 3
str1=11011
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=3;seq[2]=1;seq[3]=4;seq[4]=0;
The length is 5
str1=110000011
str2=0110111
the common subsequence is:11011
The length is 4
str1=11011
str2=000110001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=3;seq[2]=4;seq[3]=1;seq[4]=0;
The length is 5
str1=110000011
str2=0110111
the common subsequence is:11011
The length is 4
str1=11011
str2=000110001
the common subsequence is:1101
The length is 4
str1=1101
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=3;seq[2]=4;seq[3]=0;seq[4]=1;
The length is 6
str1=110000011
str2=000110001
the common subsequence is:110001
The length is 5
str1=110001
str2=010111001
the common subsequence is:11001
The length is 4
str1=11001
str2=0110111
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=4;seq[2]=0;seq[3]=3;seq[4]=1;
The length is 6
str1=110000011
str2=000110001
the common subsequence is:110001
The length is 4
str1=110001
str2=0110111
the common subsequence is:1101
The length is 4
str1=1101
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=4;seq[2]=3;seq[3]=0;seq[4]=1;
The length is 6
str1=110000011
str2=000110001
the common subsequence is:110001
The length is 4
str1=110001
str2=0110111
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=4;seq[2]=3;seq[3]=1;seq[4]=0;
The length is 6
str1=110000011
str2=000110001
the common subsequence is:110001
The length is 5
str1=110001
str2=01010000
the common subsequence is:11000
The length is 3
str1=11000
str2=0110111
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=4;seq[2]=1;seq[3]=3;seq[4]=0;
The length is 6
str1=110000011
str2=000110001
the common subsequence is:110001
The length is 5
str1=110001
str2=01010000
the common subsequence is:11000
The length is 4
str1=11000
str2=010111001
the common subsequence is:1100
The length is 3
str1=1100
str2=0110111
the common subsequence is:110
the sequence is:
seq[0]=2;seq[1]=4;seq[2]=1;seq[3]=0;seq[4]=3;
The length is 4
str1=0110111
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
The length is 3
str1=011
str2=010111001
the common subsequence is:011
The length is 3
str1=011
str2=000110001
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=1;seq[2]=2;seq[3]=0;seq[4]=4;
The length is 5
str1=0110111
str2=110000011
the common subsequence is:11011
The length is 3
str1=11011
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=2;seq[2]=1;seq[3]=0;seq[4]=4;
The length is 5
str1=0110111
str2=110000011
the common subsequence is:11011
The length is 4
str1=11011
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=000110001
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=2;seq[2]=0;seq[3]=1;seq[4]=4;
The length is 5
str1=0110111
str2=110000011
the common subsequence is:11011
The length is 4
str1=11011
str2=010111001
the common subsequence is:1101
The length is 4
str1=1101
str2=000110001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=2;seq[2]=0;seq[3]=4;seq[4]=1;
The length is 5
str1=0110111
str2=110000011
the common subsequence is:11011
The length is 4
str1=11011
str2=000110001
the common subsequence is:1101
The length is 4
str1=1101
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=2;seq[2]=4;seq[3]=0;seq[4]=1;
The length is 5
str1=0110111
str2=110000011
the common subsequence is:11011
The length is 4
str1=11011
str2=000110001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=2;seq[2]=4;seq[3]=1;seq[4]=0;
The length is 6
str1=0110111
str2=010111001
the common subsequence is:011111
The length is 4
str1=011111
str2=110000011
the common subsequence is:1111
The length is 2
str1=1111
str2=01010000
the common subsequence is:11
The length is 2
str1=11
str2=000110001
the common subsequence is:11
the sequence is:
seq[0]=3;seq[1]=0;seq[2]=2;seq[3]=1;seq[4]=4;
The length is 6
str1=0110111
str2=010111001
the common subsequence is:011111
The length is 3
str1=011111
str2=01010000
the common subsequence is:011
The length is 3
str1=011
str2=110000011
the common subsequence is:011
The length is 3
str1=011
str2=000110001
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=0;seq[2]=1;seq[3]=2;seq[4]=4;
The length is 6
str1=0110111
str2=010111001
the common subsequence is:011111
The length is 3
str1=011111
str2=01010000
the common subsequence is:011
The length is 3
str1=011
str2=000110001
the common subsequence is:011
The length is 3
str1=011
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=0;seq[2]=1;seq[3]=4;seq[4]=2;
The length is 6
str1=0110111
str2=010111001
the common subsequence is:011111
The length is 4
str1=011111
str2=000110001
the common subsequence is:0111
The length is 3
str1=0111
str2=01010000
the common subsequence is:011
The length is 3
str1=011
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=0;seq[2]=4;seq[3]=1;seq[4]=2;
The length is 6
str1=0110111
str2=010111001
the common subsequence is:011111
The length is 4
str1=011111
str2=000110001
the common subsequence is:0111
The length is 3
str1=0111
str2=110000011
the common subsequence is:011
The length is 3
str1=011
str2=01010000
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=0;seq[2]=4;seq[3]=2;seq[4]=1;
The length is 5
str1=0110111
str2=000110001
the common subsequence is:01101
The length is 4
str1=01101
str2=110000011
the common subsequence is:1101
The length is 4
str1=1101
str2=010111001
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=4;seq[2]=2;seq[3]=0;seq[4]=1;
The length is 5
str1=0110111
str2=000110001
the common subsequence is:01101
The length is 5
str1=01101
str2=010111001
the common subsequence is:01101
The length is 4
str1=01101
str2=110000011
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=3;seq[1]=4;seq[2]=0;seq[3]=2;seq[4]=1;
The length is 5
str1=0110111
str2=000110001
the common subsequence is:01101
The length is 5
str1=01101
str2=010111001
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=4;seq[2]=0;seq[3]=1;seq[4]=2;
The length is 5
str1=0110111
str2=000110001
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 4
str1=0110
str2=010111001
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=4;seq[2]=1;seq[3]=0;seq[4]=2;
The length is 5
str1=0110111
str2=000110001
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
The length is 3
str1=011
str2=010111001
the common subsequence is:011
the sequence is:
seq[0]=3;seq[1]=4;seq[2]=1;seq[3]=2;seq[4]=0;
The length is 6
str1=000110001
str2=01010000
the common subsequence is:001000
The length is 5
str1=001000
str2=110000011
the common subsequence is:00000
The length is 2
str1=00000
str2=0110111
the common subsequence is:00
The length is 2
str1=00
str2=010111001
the common subsequence is:00
the sequence is:
seq[0]=4;seq[1]=1;seq[2]=2;seq[3]=3;seq[4]=0;
The length is 6
str1=000110001
str2=110000011
the common subsequence is:000001
The length is 5
str1=000001
str2=01010000
the common subsequence is:00000
The length is 2
str1=00000
str2=0110111
the common subsequence is:00
The length is 2
str1=00
str2=010111001
the common subsequence is:00
the sequence is:
seq[0]=4;seq[1]=2;seq[2]=1;seq[3]=3;seq[4]=0;
The length is 6
str1=000110001
str2=110000011
the common subsequence is:000001
The length is 3
str1=000001
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=01010000
the common subsequence is:001
The length is 3
str1=001
str2=010111001
the common subsequence is:001
the sequence is:
seq[0]=4;seq[1]=2;seq[2]=3;seq[3]=1;seq[4]=0;
The length is 6
str1=000110001
str2=110000011
the common subsequence is:000001
The length is 3
str1=000001
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=010111001
the common subsequence is:001
The length is 3
str1=001
str2=01010000
the common subsequence is:001
the sequence is:
seq[0]=4;seq[1]=2;seq[2]=3;seq[3]=0;seq[4]=1;
The length is 6
str1=000110001
str2=110000011
the common subsequence is:000001
The length is 5
str1=000001
str2=010111001
the common subsequence is:00001
The length is 3
str1=00001
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=01010000
the common subsequence is:001
the sequence is:
seq[0]=4;seq[1]=2;seq[2]=0;seq[3]=3;seq[4]=1;
The length is 6
str1=000110001
str2=110000011
the common subsequence is:000001
The length is 5
str1=000001
str2=010111001
the common subsequence is:00001
The length is 4
str1=00001
str2=01010000
the common subsequence is:0000
The length is 2
str1=0000
str2=0110111
the common subsequence is:00
the sequence is:
seq[0]=4;seq[1]=2;seq[2]=0;seq[3]=1;seq[4]=3;
The length is 5
str1=000110001
str2=0110111
the common subsequence is:01101
The length is 4
str1=01101
str2=110000011
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
The length is 3
str1=110
str2=010111001
the common subsequence is:110
the sequence is:
seq[0]=4;seq[1]=3;seq[2]=2;seq[3]=1;seq[4]=0;
The length is 5
str1=000110001
str2=0110111
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
The length is 3
str1=011
str2=010111001
the common subsequence is:011
the sequence is:
seq[0]=4;seq[1]=3;seq[2]=1;seq[3]=2;seq[4]=0;
The length is 5
str1=000110001
str2=0110111
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 4
str1=0110
str2=010111001
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=4;seq[1]=3;seq[2]=1;seq[3]=0;seq[4]=2;
The length is 5
str1=000110001
str2=0110111
the common subsequence is:01101
The length is 5
str1=01101
str2=010111001
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=4;seq[1]=3;seq[2]=0;seq[3]=1;seq[4]=2;
The length is 5
str1=000110001
str2=0110111
the common subsequence is:01101
The length is 5
str1=01101
str2=010111001
the common subsequence is:01101
The length is 4
str1=01101
str2=110000011
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=4;seq[1]=3;seq[2]=0;seq[3]=2;seq[4]=1;
The length is 7
str1=000110001
str2=010111001
the common subsequence is:0011001
The length is 5
str1=0011001
str2=110000011
the common subsequence is:11001
The length is 4
str1=11001
str2=0110111
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=4;seq[1]=0;seq[2]=2;seq[3]=3;seq[4]=1;
The length is 7
str1=000110001
str2=010111001
the common subsequence is:0011001
The length is 5
str1=0011001
str2=0110111
the common subsequence is:01101
The length is 4
str1=01101
str2=110000011
the common subsequence is:1101
The length is 3
str1=1101
str2=01010000
the common subsequence is:110
the sequence is:
seq[0]=4;seq[1]=0;seq[2]=3;seq[3]=2;seq[4]=1;
The length is 7
str1=000110001
str2=010111001
the common subsequence is:0011001
The length is 5
str1=0011001
str2=0110111
the common subsequence is:01101
The length is 4
str1=01101
str2=01010000
the common subsequence is:0110
The length is 3
str1=0110
str2=110000011
the common subsequence is:011
the sequence is:
seq[0]=4;seq[1]=0;seq[2]=3;seq[3]=1;seq[4]=2;
The length is 7
str1=000110001
str2=010111001
the common subsequence is:0011001
The length is 5
str1=0011001
str2=01010000
the common subsequence is:00100
The length is 3
str1=00100
str2=0110111
the common subsequence is:001
The length is 3
str1=001
str2=110000011
the common subsequence is:001
the sequence is:
seq[0]=4;seq[1]=0;seq[2]=1;seq[3]=3;seq[4]=2;
The length is 7
str1=000110001
str2=010111001
the common subsequence is:0011001
The length is 5
str1=0011001
str2=01010000
the common subsequence is:00100
The length is 4
str1=00100
str2=110000011
the common subsequence is:0000
The length is 2
str1=0000
str2=0110111
the common subsequence is:00
the sequence is:
seq[0]=4;seq[1]=0;seq[2]=1;seq[3]=2;seq[4]=3;




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