//?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?<	cin.getline（X256）;
	x.append（X）;
	cout?<	cin.getline（Y256）;
	y.append（Y）;
	int?i;
	int?*?*?a?=?new?int?*[x.size（）];
	for（i?=?0;?i?		a[i]?=?new?int[y.size（）];
	LCSlength（xya）;
	cout?<	LCS（x.size（）?-?1y.size（）?-?1xa）;
	cout?<
	for（i?=?0;?i?		delete?[]a[i];
	delete?[]a;?
	return?0;
}

void?LCSlength（string?x?string?yint?*?*?a）//用二維數(shù)組a[i][j]來記錄Xi和Yj的最長公共子序列的長度
{
	int?ij;
	for（i?=?0;?i?		a[i][0]?=?0;
	for（i?=?0;?i?		a[0][i]?=?0;
	for（i?=?1;?i?	{
		for（j?=?1;?j?		{
			if（x[i]?==?y[j]）		//②當(dāng)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]）//③當(dāng)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					//④當(dāng)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）//根據(jù)二維數(shù)組a[i][j]來輸出這個最長公共子序列
{
	if（i?==?0?||?j?==0）?return;		//①二維表中的第一列和第一行中的元素都為0不必進(jìn)行輸出操作
	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，對應(yīng)于遞歸關(guān)系的第②種情況
	{
		LCS（i?-?1j?-?1?x?a）;
		cout?<	}
	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]，對應(yīng)于遞歸關(guān)系的第③種情況
		LCS（i?-?1?j?x?a）;
	else							//a[i][j-1]?≥?a[i-1][j]，a[i][j]?=?a[i][j-1]，對應(yīng)于遞歸關(guān)系的第④種情況
		LCS（i?j?-?1?x?a）;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-03-25?22:16??最長公共子序列\(zhòng)
?????目錄???????????0??2018-03-25?22:03??最長公共子序列\(zhòng)最長公共子序列\(zhòng)
?????文件???????25608??2018-03-25?22:16??最長公共子序列\(zhòng)最長公共子序列.docx
?????目錄???????????0??2017-04-15?14:17??最長公共子序列\(zhòng)最長公共子序列\(zhòng)Debug\
?????文件????????2450??2017-04-06?16:17??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.cpp
?????文件????????4500??2017-03-31?13:16??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.dsp
?????文件?????????531??2017-03-31?13:16??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.dsw
?????文件???????58368??2017-04-16?17:50??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.ncb
?????文件???????48640??2017-04-16?17:50??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.opt
?????文件????????1341??2017-04-06?16:17??最長公共子序列\(zhòng)最長公共子序列\(zhòng)LCS.plg
?????文件????????1190??2017-03-31?13:16??最長公共子序列\(zhòng)最長公共子序列\(zhòng)ReadMe.txt
?????文件?????????290??2017-03-31?13:16??最長公共子序列\(zhòng)最長公共子序列\(zhòng)StdAfx.cpp
?????文件?????????667??2017-03-31?13:16??最長公共子序列\(zhòng)最長公共子序列\(zhòng)StdAfx.h