The longest common subsequence problem has been widely studied and used to find out the relationship between sequences. In this paper, we study the interleaving relationship between sequences, that is, we measure the relationship among three sequences, where two of those are interleaved in different ways and then the interleaved sequences are subsequently matched with the third remaining sequence, as pairwise longest common subsequence problems. Given a target sequence T and two other sequences A and B, we need to find out the LCS between M (A, B) and T , where M (A, B) denotes the merged sequence which consists of A and B. We first present an improved O((Rr + P m) log log r) time algorithm, where we consider only the matches between sequences; here |T | = n, |A| = m and |B| = r (m ≥ r); R is the total number of ordered pairs of positions at which the two strings A and T match and P denotes the total number of ordered pairs of positions at which the two strings B and T match. Basing on the same idea, we also propose an improved algorithm to solve a block constrained variation of the problem. Running time of the blocked version is O(max{Rβ log log r, P α log log r}), where α denotes the number of blocks in A and β denotes the number of blocks in B. However, these improved algorithms do not provide best output in every cases. Therefore we finally fabricate a hybrid algorithm which utilizes the advantages of our proposed algorithms and previous state of the arts algorithms to provide best output in every possible cases, from both time efficiency and space efficiency.
int MLCS_SPDP_Boundedheap(vector< int>T, vector< int>A, vector< int>B, int Tlen, int Alen, int Blen, int size)
{
vector< pair< int, int > > mylistmatchAT, mylistmatchBT;
vector< pair< int, int > > ::iterator it;
vector< < int> >Boundedheap1(Alen + 1, vector< int>(Blen + 1));
vector< vector< int > >Boundedheap2(Alen + 1, vector< int>(Blen + 1));
int glMLCS = 0, temp;
for (int i = 1; i <= Alen; i++) //AT match pair
{
for (int k = 1; k <= Tlen; k++)
{
if (A[i] == T[k])
mylistmatchAT.push_back(pair< int, int>(i, k));
}
}
for (int j = 1; j <= Blen; j++) //BT match pair
{
for (int k = 1; k <= Tlen; k++)
{
if (B[j] == T[k])
mylistmatchBT.push_back(pair< int, int>(j, k));
}
}
//hybrid
if (mylistmatchAT.size() + mylistmatchBT.size() <= Tlen) {
int layer = 1;
while (1) {
if (layer % 2 == 1) {
for (int i = 0; i <= Alen; i++)
{
for (int j = 0; j <= Blen; j++) // H(k,i)=max(H(k-1,i),H(k,i-1))
{
if (i - 1 == -1)
Boundedheap1[i][j] = Boundedheap2[i][j];
else if (layer - 1 == 0)
Boundedheap1[i][j] = Boundedheap1[i - 1][j];
else
Boundedheap1[i][j] = max(Boundedheap2[i][j], Boundedheap1[i - 1][j]);
}
for (it = mylistmatchBT.begin(); it != mylistmatchBT.end(); it++)//(*it).first = j (*it).second = k
{
if (layer == (*it).second)
{
for (int m = (*it).first - 1; m >= 0; m--)
{
Boundedheap1[i][(*it).first] = max(Boundedheap1[i][(*it).first], Boundedheap2[i][m] + 1);//boundedmax
if (glMLCS < Boundedheap1[i][(*it).first])
glMLCS = Boundedheap1[i][(*it).first];
}
}
}
if (binarysearch(mylistmatchAT, i, layer))
{
for (int j = 0; j <= Blen; j++)
{
for (int m = j; m >= 0; m--)
{
Boundedheap1[i][j] = max(Boundedheap1[i][j], Boundedheap2[i - 1][m] + 1);//boundedmax
if (glMLCS < Boundedheap1[i][j])
glMLCS = Boundedheap1[i][j];
}
}
}
}
if (layer == Tlen)
break;
++layer;
}
else {
for (int i = 0; i <= Alen; i++)
{
for (int j = 0; j <= Blen; j++) // H(k,i)=max(H(k-1,i),H(k,i-1))
{
if (i - 1 == -1)
Boundedheap2[i][j] = Boundedheap1[i][j];
else if (layer - 1 == 0)
Boundedheap2[i][j] = Boundedheap2[i - 1][j];
else
Boundedheap2[i][j] = max(Boundedheap1[i][j], Boundedheap2[i - 1][j]);
}
for (it = mylistmatchBT.begin(); it != mylistmatchBT.end(); it++)//(*it).first = j (*it).second = k
{
if (layer == (*it).second)
{
for (int m = (*it).first - 1; m >= 0; m--)
{
Boundedheap2[i][(*it).first] = max(Boundedheap2[i][(*it).first], Boundedheap1[i][m] + 1);//boundedmax
if (glMLCS < Boundedheap2[i][(*it).first])
glMLCS = Boundedheap2[i][(*it).first];
}
}
}
if (binarysearch(mylistmatchAT, i, layer))
{
for (int j = 0; j <= Blen; j++)
{
for (int m = j; m >= 0; m--)
{
Boundedheap2[i][j] = max(Boundedheap2[i][j], Boundedheap1[i - 1][m] + 1);//boundedmax
if (glMLCS < Boundedheap2[i][j])
glMLCS = Boundedheap2[i][j];
}
}
}
}
if (layer == Tlen)
break;
++layer;
}
}
return glMLCS;
}
else
return MLCS_PengSparse(T, A, B, Tlen, Alen, Blen, size);
}