//?LCS.cpp?:?定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#include?“stdafx.h“
#define?SLANT?0
#define?VERTICAL?-1
#define?CROSSWISE?1




void?lengthLCS（string?&xint?xLenstring?&yint?yLenint?**recordint?**direct）
{
	int?ij;
	i?=?j?=?0;
	
	for（i=0?;?i		record[i][0]?=?0;
	}
	for（j=0?;?j		record[0][j]?=?0;
	}

	for（i=1?;?i		for（j=1?;?j			if（x[i-1]?==?y[j-1]）{
				record[i][j]?=?record[i-1][j-1]?+?1;
				direct[i][j]?=?SLANT;
			}else{
				if（record[i-1][j]?>=?record[i][j-1]）{
					record[i][j]?=?record[i-1][j];
					direct[i][j]?=?VERTICAL;
				}else{
					record[i][j]?=?record[i][j-1];
					direct[i][j]?=?CROSSWISE;
				}
			}
		}
	}
}

void?printLCS（string?xint?xLenint?**directint?iint?j）
{
	if（0==i?||?0==j）{
		return;
	}
	if（SLANT?==?direct[i][j]）{
		printLCS（xxLendirecti-1j-1）;
		cout<	}else?if（VERTICAL?==?direct[i][j]）{
		printLCS（xxLendirecti-1j）;
	}else{
		printLCS（xxLendirectij-1）;
	}
}

void?generateString（string?&xstring?&yint?length）
{
	string?s?=?“ABCDEFGHIJKLMNOPQRSTUVWXYZ“;
	for（int?i=0?;?i		int?num1?=?rand（）%26;
		int?num2?=?rand（）%26;
		string?s1（1s[num1]）;
		x?=?x.append（s1）;
		string?s2（1s[num2]）;
		y?=?y.append（s2）;
	}
	return;
}

int?_tmain（int?argc?_TCHAR*?argv[]）
{
	string?xy;
	int?length?=?10000;
	generateString（xylength）;
	/*string?x?=?“ABCBDAB“;
	string?y?=?“BDCABA“;*/
	int?xLen?=?x.length（）;
	int?yLen?=?y.length（）;
	int?**record?=?（int**）malloc（（yLen+1）*sizeof（int*））;
	int?**direct?=?（int**）malloc（（yLen+1）*sizeof（int*））;
	for（int?i=0?;?i<=xLen?;?++i）{
		record[i]?=?（int*）malloc（（xLen+1）*sizeof（int））;
		direct[i]?=?（int*）malloc（（xLen+1）*sizeof（int））;
	}
	
	lengthLCS（xxLenyyLenrecorddirect）;
	printLCS（xxLendirectxLenyLen）;
	
	getchar（）;
	return?0;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-12-07?10:02??LCS\
?????目錄???????????0??2013-12-07?08:22??LCS\Debug\
?????文件???????61440??2013-12-07?08:48??LCS\Debug\LCS.exe
?????文件??????743804??2013-12-07?08:48??LCS\Debug\LCS.ilk
?????文件??????904192??2013-12-07?08:48??LCS\Debug\LCS.pdb
?????目錄???????????0??2013-12-07?06:44??LCS\ipch\
?????目錄???????????0??2013-12-07?06:44??LCS\ipch\lcs-48a42a15\
?????文件????15532032??2013-12-07?10:00??LCS\ipch\lcs-48a42a15\lcs-65ebb98e.ipch
?????目錄???????????0??2013-12-13?18:22??LCS\LCS\
?????文件?????6180864??2013-12-07?10:02??LCS\LCS.sdf
?????文件?????????876??2013-09-22?18:17??LCS\LCS.sln
?????文件???????14848??2013-12-07?10:01??LCS\LCS.suo
?????目錄???????????0??2013-12-07?08:48??LCS\LCS\Debug\
?????文件????????2962??2013-12-07?08:48??LCS\LCS\Debug\cl.command.1.tlog
?????文件???????20326??2013-12-07?08:48??LCS\LCS\Debug\CL.read.1.tlog
?????文件????????1738??2013-12-07?08:48??LCS\LCS\Debug\CL.write.1.tlog
?????文件?????????406??2013-09-22?18:37??LCS\LCS\Debug\LCS.exe.embed.manifest
?????文件?????????472??2013-12-07?06:45??LCS\LCS\Debug\LCS.exe.embed.manifest.res
?????文件?????????381??2013-12-07?08:48??LCS\LCS\Debug\LCS.exe.intermediate.manifest
?????文件??????????77??2013-12-07?08:48??LCS\LCS\Debug\LCS.lastbuildstate
?????文件????????2206??2013-12-07?08:48??LCS\LCS\Debug\LCS.log
?????文件???????93725??2013-12-07?08:48??LCS\LCS\Debug\LCS.obj
?????文件?????7929856??2013-12-07?06:45??LCS\LCS\Debug\LCS.pch
?????文件?????????196??2013-09-22?18:37??LCS\LCS\Debug\LCS_manifest.rc
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link-cvtres.read.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link-cvtres.write.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link.2784-cvtres.read.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link.2784-cvtres.write.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link.2784.read.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link.2784.write.1.tlog
?????文件???????????2??2013-12-07?08:48??LCS\LCS\Debug\link.2952-cvtres.read.1.tlog
............此處省略29個(gè)文件信息