最长公共子序列的动态规划算法

利用动态规划法求出两个序列的最长公共子序列，内含C++源代码和实验报告

// LCS.cpp : Defines the entry point for the console application.
//

#include “stdafx.h“
#include “iostream“
#include “string“
using namespace std;

void LCSlength（string x string yint * * a）;
void LCS（int i int j string x int * * a）;

int main（int argc char* argv[]）
{
	/*x = “zhejiang university of technology“	
	y = “zhejiang university city college“;
	X={ABCBDAB} Y={BDCABA};*/
	string x = “ “;
	string y = “ “;
	char X[256];
	char Y[256];
	cout << “请输入第一个字符串序列:“ << endl;
	cin.getline（X256）;
	x.append（X）;
	cout << “请输入第二个字符串序列:“ << endl;
	cin.getline（Y256）;
	y.append（Y）;
	int i;
	int * * a = new int *[x.size（）];
	for（i = 0; i < x.size（）; i ++）
		a[i] = new int[y.size（）];
	LCSlength（xya）;
	cout << “最长公共子序列:“ << endl;
	LCS（x.size（） - 1y.size（） - 1xa）;
	cout << endl << endl;

	for（i = 0; i < x.size（）; i++）
		delete []a[i];
	delete []a; 
	return 0;
}

void LCSlength（string x string yint * * a）//用二维数组a[i][j]来记录Xi和Yj的最长公共子序列的长度
{
	int ij;
	for（i = 0; i < x.size（）; i++）
		a[i][0] = 0;
	for（i = 0; i < y.size（）; i++）	//①当i = 0或者j = 0时，a[i][j] = 0
		a[0][i] = 0;
	for（i = 1; i < x.size（）; i++）
	{
		for（j = 1; j < y.size（）; j++）
		{
			if（x[i] == y[j]）		//②当i > 0，j > 0，xi = yj时，a[i][j] = a[i-1][j-1] + 1
			{
				a[i][j] = a[i - 1][j - 1] + 1;
			}
			else if（a[i - 1][j] >= a[i][j - 1]）//③当i > 0，j > 0，xi≠yi，a[i-1][j] > a[i][j-1]时，a[i][j] = a[i-1][j]
			{
				a[i][j] = a[i - 1][j];
			}
			else					//④当i > 0，j > 0，xi≠yi，a[i][j-1] ≥ a[i-1][j]时，a[i][j] = a[i][j-1]
			{
				a[i][j] = a[i][j - 1];
			}
		}
	}
}


void LCS（int i int j string x int * * a）//根据二维数组a[i][j]来输出这个最长公共子序列
{
	if（i == 0 || j ==0） return;		//①二维表中的第一列和第一行中的元素都为0不必进行输出操作
	if（a[i - 1][j - 1] == a[i - 1][j] 
	   && a[i - 1][j - 1] == a[i][j - 1] 
	   && a[i - 1][j] == a[i][j - 1] 
	   && a[i][j] == a[i - 1][j - 1] + 1）
	   //a[i-1][j-1] = a[i-1][j] = a[i][j-1]，而且a[i][j] = a[i-1][j-1] + 1，对应于递归关系的第②种情况
	{
		LCS（i - 1j - 1 x a）;
		cout << x[i];				//此时x[i]=y[j]输出这个值
	}
	else if（a[i - 1][j] > a[i][j - 1]）//a[i-1][j] > a[i][j-1]，a[i][j] = a[i-1][j]，对应于递归关系的第③种情况
		LCS（i - 1 j x a）;
	else							//a[i][j-1] ≥ a[i-1][j]，a[i][j] = a[i][j-1]，对应于递归关系的第④种情况
		LCS（i j - 1 x a）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-03-25 22:16  最长公共子序列\
     目录           0  2018-03-25 22:03  最长公共子序列\最长公共子序列\
     文件       25608  2018-03-25 22:16  最长公共子序列\最长公共子序列.docx
     目录           0  2017-04-15 14:17  最长公共子序列\最长公共子序列\Debug\
     文件        2450  2017-04-06 16:17  最长公共子序列\最长公共子序列\LCS.cpp
     文件        4500  2017-03-31 13:16  最长公共子序列\最长公共子序列\LCS.dsp
     文件         531  2017-03-31 13:16  最长公共子序列\最长公共子序列\LCS.dsw
     文件       58368  2017-04-16 17:50  最长公共子序列\最长公共子序列\LCS.ncb
     文件       48640  2017-04-16 17:50  最长公共子序列\最长公共子序列\LCS.opt
     文件        1341  2017-04-06 16:17  最长公共子序列\最长公共子序列\LCS.plg
     文件        1190  2017-03-31 13:16  最长公共子序列\最长公共子序列\ReadMe.txt
     文件         290  2017-03-31 13:16  最长公共子序列\最长公共子序列\StdAfx.cpp
     文件         667  2017-03-31 13:16  最长公共子序列\最长公共子序列\StdAfx.h