用动态规划思想求解最长公共子串

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列

#include
#include
using namespace std;

string xy;//xy用来存放字符序列
int **c**bmn;
/*m，n分别存储字符串xy的长度数组c[i][j]存储Xi和Yj得最长公共子序列的长度，
b[i][j]记录c[i][j]的值是有哪一个子问题的解得到的*/

void LCSLength（int mint nstring xstring yint **cint**b）;
void LCS（int iint jstring xint **b）;
void Initialize（）;//对数组bc动态分配空间以及对其进行初始化
void ReadCommand（char &cmd）;
void Interpret（char &cmd）;
void Realese（）;//释放指针
void Display（）;


int main（）
{
	char cmd;	
	do
	{
		ReadCommand（cmd）;
		Interpret（cmd）;
	}while（cmd!=‘q‘&&cmd!=‘Q‘）;
	return 0;
}

void ReadCommand（char &cmd）
{
	system（“cls“）;   //清屏
	cout<<“\n--------------------------------------------------------------------------\n“;
	cout<<“\n\t\t\t\t操  作  提  示“;
	cout<<“\n-----------------------------------------------