Longest Common Subsequence

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;