lcs.cpp

用动态规划法实现查找两字符串的公共子序列。是算法中的一个重要问题。

//最长公共子序列问题（动态规划法）

#include <iostream>
#include <string>
#include <stack>

using namespace std;

void LCS_L(char *x, char *y, int m, int n, int *c, char *b)
{
	//第一行、第一列置为0
	for (int i=0; i<m; i++)
	{
		c[i * n] = 0;
	}
	for (int j=1; j<n; j++)
	{
		c[j] = 0;	
	}
	
	for (i=1; i<m; i++)
	{
		for (j=1; j<n; j++)
		{
			if (x[i-1] == y[j-1])
			{
				c[i*n + j] = c[(i-1)*n + j-1] + 1;
				b[i*n + j] = 'E';                        //指示标志为"Equal";箭头指向左上
			}
			else if (c[(i-1)*n + j] >= c[i*n + j-1])
			{
				c[i*n + j] = c[(i-1)*n + j];
				if (c[(i-1)*n + j] > c[i*n + j-1])
				{
					b[i*n + j] = 'U';                    //指示标志为"Up";箭头指向上
				}
				else
				{
					b[i*n + j] = 'B';                    //指示标志为"Both";一个箭头指向上，另一个指向左
				}		
			}
			else
			{
				c[i*n + j] = c[i*n + j-1];
				b[i*n + j] = 'L';                        //指示标志为"Left";箭头指向左
			}
		}
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////
void LCS_Output(char *b, char *x, int i, int j, const int n, stack<char> s)
{
	if (i==0 || j==0)
	{
		while (!s.empty())
		{
			cout << s.top();
			s.pop();
		}

		return;
	}

	if (b[i*n + j] == 'E')                      //x[i] == y[j]
	{	
		s.push(x[i-1]);

		LCS_Output(b, x, i-1, j-1, n, s);
	}
	else if (b[i*n + j] == 'L')                //x[i] != y[j]; c[i-1][j] < c[i][j-1]
	{
		LCS_Output(b, x, i, j-1, n, s);
	}
	else if (b[i*n + j] == 'U')                //x[i] != y[j]; c[i-1][j] > c[i][j-1]
	{
		LCS_Output(b, x, i-1, j, n, s);
	}
	else                                       //x[i] != y[j]; c[i-1][j] == c[i][j-1]
	{
		stack<char> temp_s = s;

		LCS_Output(b, x, i, j-1, n, temp_s);

		cout << "\n";

		LCS_Output(b, x, i-1, j, n, s);
	}

}

/////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
	char x[] = "ABCBDAB";
	char y[] = "BDCABA";
//	char y[] = "ABCBDABA";
//	char y[] = "";

	stack<char> s;

	int m = strlen(x) + 1;
	int n = strlen(y) + 1;

	int *c = new int[m * n];
	char *b = new char[m * n];

	LCS_L(x, y, m, n, c, b);
	LCS_Output(b, x, m-1, n-1, n, s);

	cout << '\n';

	for (int i=0; i<m; i++)
	{
		for (int j=0; j<n; j++)
		{
			cout << c[i*n + j] << '\t';
		}
		cout << '\n';
	}

	for (i=0; i<m; i++)
	{
		for (int j=0; j<n; j++)
		{
			cout << b[i*n + j] << '\t';
		}
		cout << '\n';
	}

	delete []c;
	delete []b;

	cin.get();
}