lcs.cpp

本程序实现的功能是给出了两个序列

#include <iostream>
#include <string.h>
#define MAXSIZE 100
using namespace std;
int C[MAXSIZE][MAXSIZE] ; //记录序列X和Y的LCS的长度
int B[MAXSIZE][MAXSIZE] ;//记录二维数组C是通过哪一个子问题的值求得的,以决定搜索的方向:1-对角线方向;2-向上;3-向左;4-向上或向左
char LCS[MAXSIZE];
int len = 0;

/*函数名:LCS_Len
功能:自底向上进行递推计算C[i][j],并确定B中的搜索方向
若i =0 或 j =0 则C[i][j] = 0;
若i,j > 0且x[i] = y[j] 则C[i][j] = C[i-1][j-1] + 1; 
若i,j > 0且x[i]!= y[j] 则C[i][j] = max{C[i-1][j],C[i][j-1])
输入:两个序列X和Y
输出:二维数组B和C*/
void LCS_Len(char* X, char* Y)
{
int m = strlen(X)-1;
int n = strlen(Y)-1;
for(int i = 0; i < m; i++ ) C[i][0] = 0;
for(int j = 1; j < n; j++ ) C[0][j] = 0;
for(i = 1;i <= m; i++ )
for(j = 1; j <= n; j++ )
{
if( X[i] == Y[j] )
{
C[i][j] = C[i-1][j-1] + 1;
B[i][j] = 1;
}
else if ( C[i-1][j] > C[i][j-1] )
{
C[i][j] = C[i-1][j];
B[i][j] = 2;
}
else if ( C[i-1][j] < C[i][j-1] )
{
C[i][j] = C[i][j-1];
B[i][j] = 3;
}
else /*C[i-1][j] == C[i][j-1]*/
{
C[i][j] = C[i-1][j];
B[i][j] = 4;
}
}
}
/*
函数名:Fine_All_LCS
功能:回溯法递归输出所有的LCS
参数说明:
Direction : 记录搜索方向的二维数组，1-对角线方向;2-向上;3-向左;4-向上或向左
X : 一个序列
i,j : 待搜索的下标，初始值为两个序列的长度
len: 记录当前LCS的长度
lcslen: LCS的长度
LCS:记录当前得到的LCS字符*/

void Find_All_LCS(int Direction[MAXSIZE][MAXSIZE], char* X, int i, int j, int curlen, int lcslen)
{
if(i>=0 && j>=0)
{
if(len == lcslen)//如果当前lcs的长度等于已知的LCS的长度则输出子序列
{
for( int k = len - 1 ; k >= 0 ; k-- )
cout << LCS[k];
cout << "\n";
}
else 
{
if(Direction[i][j] == 1)
{
LCS[curlen] = X[i];
len++; //子序列长度加1
Find_All_LCS(Direction, X, i-1, j-1, curlen + 1, lcslen);//沿对角线方向搜索
len--; //回溯
}
else if(Direction[i][j] == 2)
{
Find_All_LCS(Direction, X, i-1, j, curlen, lcslen);
}
else if(Direction[i][j] == 3)
{
Find_All_LCS(Direction, X, i, j-1, curlen, lcslen);
}
else //递归调用Find_All_LCS分别沿两个不同的方向搜索
{
Find_All_LCS(Direction, X, i, j-1, curlen, lcslen);
Find_All_LCS(Direction, X, i-1, j, curlen, lcslen);
}
}
}
}

int main()
{
char *x, *y;
x = " BCBDABC";//0单元未用,下标从1开始
y = " BDCABA";
int m = (int)strlen(x)-1;
int n = (int)strlen(y)-1;
int lcslen;

cout << "x =" << x << endl;
cout << "y =" << y << endl;

cout << "The longest common sequence as following:" << endl;

LCS_Len(x, y);
lcslen = C[m][n];
Find_All_LCS(B, x, m, n, 0, lcslen); 
cout << "OK!";
return 0;
}