最长公共子序列.cpp

动态规划解一系列经典问题

//最长公共子序列

#include <iostream.h>
#include <string.h>
#define N 100

void LCSLength(int m, int n, char *x, char *y, int c[N][N], int b[N][N])
{
	for (int i=1; i<=m; i++)
		for (int 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]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
}

void LCS(int i, int j, char *x, int b[N][N])
{
	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]==2) LCS(i-1, j, x, b);
	else LCS(i, j-1, x, b);
}

void main()
{
	char *x="alkgjongsfgna", *y="slakjowarogjos";
	int m=strlen(x), n=strlen(y), a[N][N]={0}, b[N][N]={0};
	LCSLength(m, n, x, y, a, b);
	LCS(m, n, x, b);
	cout<<endl;
}