// 最長公共子序列.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h"
#include "iostream"

using namespace std;

//用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度,b[i][j]記錄c[i][j]的值是由哪一個子問題的解得到的，這在構造最長公共
//子序列時要用到。b[i][j]為'-1'時，表示Xi和Yi的最長公共子序列是由X(i-1)和Y(j-1)的最長公共子序列在尾部加上xi所得到的
//子序列。b[i][j]為'0'時，表示Xi和Yi的最長公共子序列與X(i-1)和Y(j)的最長公共子序列相同。b[i][j]為'1'時，表示Xi和Yi
//的最長公共子序列與X(i)和Y(j-1)的最長公共子序列相同。
//問題的最優解，即X[1:m]和Y[1:n]的最長公共子序列的長度記錄于c[m][n]中。

int c[100][100],b[100][100];

void LCSLength(int m,int n,char *x,char *y,int c[][100],int b[][100])
{
	int i,j;
	for (i=1;i<=m;i++)
		c[i][0]=0;
	for(i=1;i<=n;i++)
		c[0][i]=0;

	for(i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			if (x[i]==y[j])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]='1';
			}
			else if (c[i-1][j]>=c[i][j-1])
			    {
					c[i][j]=c[i-1][j];
					b[i][j]='0';
			     }
			else 
			{
				c[i][j]=c[i][j-1];
				b[i][j]='-1';
			}		        

		}
}

void LCS(int i,int j,char *x,int b[][100])
{
	if(i == 0 || j == 0)
		return;
	if(b[i][j] == '1')
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i];
	}
	else if (b[i][j] == '0')
	{
		LCS(i-1,j,x,b);
	} 
	else
	{
		LCS(i,j-1,x,b);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	char *x=" ABCBDAB";
	char *y=" BDCABA";
	int m=(int)strlen(x);
	int n=(int)strlen(y);
    
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			c[i][j]='-2';
			b[i][j]='-2';
		}
	
	LCSLength(m,n,x,y,c,b);
	LCS(m,n,x,b);

	getchar();
	return 0;
}