动态规划——最长公共子序列

题目

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。

比如字符串1：BDCABA；字符串2：ABCBDAB

则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

思路

参考这篇博客

https://blog.csdn.net/hrn1216/article/details/51534607

 

代码如下：

#include<iostream> 
#include<cstring> 
#define MAX_LEN 100 
using namespace std; 

char x[MAX_LEN]; 
//两个子序列 
char y[MAX_LEN];
int xLen=0; 
//两个子序列的长度 
int yLen=0;
char z[MAX_LEN];
//保存最长公共子序列 
int c[MAX_LEN][MAX_LEN];
//记录LCS[i][j] 的个数 
void getLCS() 
{ 
	//构造二维表 
	for(int i=0; i<=xLen; i++)
	{
		for(int j=0; j<=yLen; j++) 
		{
			if(i==0||j==0)
			{
				c[i][j]=0;
			}
			else if(i>0&&j>0&&x[i]==y[j]) 
			{
				c[i][j]=c[i-1][j-1]+1;
			}
			else 
			{
				c[i][j]=c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1];
			}
		}
	}
	int num=0; 
	int i=xLen;
	int j=yLen; 
	//回溯获得最长子序列 

	while(i!=0&&j!=0)
	{
		if(x[i]==y[j])
		{
			z[++num]=x[i];
			i--;
			j--;
		}
		else
		{
			if(c[i-1][j]>=c[i][j-1])
			{
				i--;
				z[++num]=x[i];
			}
			else
			{
				j--;
				z[++num]=y[j];
			}
		}
	}
}
int main() 
{
	cin>>xLen;
	//下标从 i=1 开始 
	for(int i=1; i<=xLen; i++)
	{
		cin>>x[i]; 
	}
	cin>>yLen; 
	for(int i=1; i<=yLen; i++)
	{
		cin>>y[i];
	}
	getLCS();
	//获得最长公共子序列 
	cout<<"最长公共子序列包含元素个数为："<<c[xLen][yLen]<<endl; 
	cout<<"最长公共子序列为："; 
	for(int i=c[xLen][yLen];i>0;i--)
	{
		cout<<z[i]<<" "; 
	}
	cout<<endl;
	system("pause");
	return 0;
}