Longest Common Subsequence(experiment)
A. Second Edition
I am using the LCS to do a series meaningless little experiments.
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?
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.
กก
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;