最长公共子序列（LCS）

参考：

http://blog.chinaunix.net/uid-26548237-id-3374211.html

http://www.ahathinking.com/archives/115.html

http://blog.csdn.net/v_july_v/article/details/6695482

最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

<pre name="code" class="cpp">//只能打印一个最长公共子序列
#include <iostream>
using namespace std;

const int X = 100, Y = 100;        //串的最大长度
char result[X+1];                    //用于保存结果
int count=0;                        //用于保存公共最长公共子序列的个数

/*功能：计算最优值
*参数：
*        x:字符串x
*        y:字符串y
*        b:标志数组
*        xlen:字符串x的长度
*        ylen:字符串y的长度
*返回值：最长公共子序列的长度
*
*/
int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen) 
{
	int i = 0;
	int j = 0;

	int c[X+1][Y+1];//为什么矩阵c行数为X+1，列数为Ｙ＋１，就是为了避免讨论边界情况
	for (i = 0; i<=xlen; i++) 
	{
		c[i][0]=0;
	} 
	for (i = 0; i <= ylen; i++ ) 
	{
		c[0][i]=0;
	}
	for (i = 1; i <= xlen; i++) //这里i，j从1开始取就避免了讨论边界的特殊情况
	{

		for (j = 1; j <= ylen; j++) 
		{
			if (x[i - 1] == y[j - 1])
			{
				c[i][j] = c[i-1][j-1]+1; 
				b[i][j] = 1;//1标记按对角线移动
			}
			else if (c[i-1][j] > c[i][j-1]) 
			{
				c[i][j] = c[i-1][j]; 
				b[i][j] = 2;//标记向上移动
			}
			else 
			{
				c[i][j] = c[i][j-1]; 
				b[i][j] = 3;//标记向左移动
			}

		}
	}
	cout << "计算最优值效果图如下所示：" << endl;
	for(i = 1; i <= xlen; i++)
	{
		for(j = 1; j <= ylen; j++)
		{
			cout << c[i][j] << " ";
		}
		cout << endl;
	}
	return c[xlen][ylen];//返回最终计算出的最长子序列的长度
}

void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_Len)
{
	if (i ==0 || j==0) //这里i,j分别对应的是xlen，ylen
	{
		return;
	}
	if(b[i][j]== 1) 
	{ 
		current_Len--;
		result[current_Len]=x[i- 1];//把最长子序列保存到result数组中，因为是从后往前保存的所以保存到result中也是从后往前保存的
		Display_Lcs(i-1, j-1, x, b, current_Len);
	}
	else if(b[i][j] == 2) 
	{
		Display_Lcs(i-1, j, x, b, current_Len);
	}
	else 

	{
		Display_Lcs(i, j-1, x, b, current_Len);

	}
}
//也可以不用递归方法，来打印出最长子序列
void Display_Lcs2(int i,int j,string x,int b[][Y+1],int current_Len)
{
	while(i&&j)//注意这里要进行i、j的边界检测
	{
		if(b[i][j]== 1) 
		{ 
			current_Len--;
			result[current_Len]=x[i- 1];//把最长子序列保存到result数组中，因为是从后往前保存的所以保存到result中也是从后往前保存的
			i--;
			j--;
		}
		else if(b[i][j] == 2) 
		{
			i--;
		}
		else 

		{
			j--;

		}
	}
}

int main(int argc, char* argv[])
{
	 string x = "ABCBDAB";
     string y = "BDCABA";
	int xlen = x.length();
	int ylen = y.length();

	int b[X + 1][Y + 1];

	int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );

	cout <<"最长公共子序列的长度: "<< lcs_max_len << endl;

	Display_Lcs2( xlen, ylen, x, b, lcs_max_len );

	//打印结果如下所示
	cout<< "最长公共子序列: ";
	for(int i = 0; i < lcs_max_len; i++)
	{
		cout <<result[i];
	}
	cout << endl;
	return 0;
}

在LCS问题中，如果仅仅要求求出LCS的长度，而不要求输出序列，那么由于每步迭代都只用到了前面的状态，之前的信息便无用了，我们就可以使用滚动数组了

#include <iostream>
using namespace std;

/* 滚动数组 */

int dp[2][21];  //存储LCS长度，这里用两行就足够了，不停的在两行之间翻转0.

char X[21];
char Y[21];
int i, j, k;

void main()
{
    cin.getline(X,20);
    cin.getline(Y,20);

    int xlen = strlen(X);
    int ylen = strlen(Y);

    for(i = 1; i <= xlen; ++i)
    {
        k = i & 1;//这里做位与运算，便于翻转k
        for(j = 1; j <= ylen; ++j)
        {
            if(X[i-1] == Y[j-1])
            {
                dp[k][j] = dp[k^1][j-1] + 1;//k与1做异或运算调整行号，dp[k]与dp[k^1]则分别在不同行
            }
			else if(dp[k][j-1] > dp[k^1][j])
            {
                dp[k][j] = dp[k][j-1];
            }else
            {
                dp[k][j] = dp[k^1][j];
            }
        }
    }
    printf("len of LCS is: %d\n", dp[k][ylen]);
}

秒客网

最长公共子序列（LCS）

相关文章