最长公共子序列问题

#include<bits/stdc++.h>
using namespace std;

/*
	最长公共子序列问题
	2019-12-15 12:48:14

*/

char x[100];
char y[100];
int dp[100][100];
int b[100][100];

int LCS(char x[], char y[],int m, int n)
{
	// 初始化
	for (int i = 0; i <= m; i++) // 初始化第一列 
	{
		dp[i][0] = 0;
	}
	for (int i = 0; i <= n; i++)
	{
		dp[0][i] = 0; //  初始化第一行
	}

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (x[i] == y[j])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				b[i][j] = 1;
			}
			else if (dp[i - 1][j] >= dp[i][j - 1])
			{
				dp[i][j] = dp[i - 1][j];
				b[i][j] = 2;
			}
			else
			{
				dp[i][j] = dp[i][j - 1];
				b[i][j] = 3;

			}
		}
	}

	return dp[m][n];

}


// 根据b矩阵得出最长公共子序列
stack<char> s;
void getLCS(int i, int j)
{
	// basecase
	if (i > 0 && j > 0)
	{
		if (b[i][j] == 1) {
			s.push(x[i]);
			getLCS(i - 1, j - 1);
		}
		if (b[i][j] == 2)
		{
			getLCS(i - 1, j);
		}
		if (b[i][j] == 3)
		{
			getLCS(i, j - 1);
		}

	}
	
}



int main()
{
	int m, n = 0;
	cin >> m >> n;

	for (int i = 1; i <= m; i++)
	{
		cin >> x[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> y[i];
	}

	cout << LCS(x, y, m, n) << endl;



	//dp矩阵
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			cout << dp[i][j] << "\t";
		}
		cout << endl;
	}
	cout << endl;


	getLCS(m, n);

	//打印最长公共子序列
	while (!s.empty())
	{
		cout << s.top() << endl;
		s.pop();
	}

	system("pause");

	return 0;

}