lcs.cpp

最大公共子序列

#include <iostream>
using namespace std;
#define max(a,b) (((a) > (b)) ? (a) : (b))

int c[100][100];
char b[100][100];
int len = 0;
static char k[100];
int O= 0;

int LCS(char x[],char y[],int i,int j )
{
	int c;
	O++;
	if(i==-1||j==-1)
		c = 0;
	else if(x[i]==y[j])
	{
		c =  1+LCS(x,y,i-1,j-1);		
		k[c] = x[i];
		
	}
	else
	{
		int c1 = LCS(x,y,i,j-1);
		int c2 = LCS(x,y,i-1,j);
		c = c1;
		if(c1<c2)
			c = c2;
	}
	return c;
}


void LCS1(char x[],char y[],int m,int n)
{
	O= 0;
	int i,j;
	for(i=1;i<=m;i++)
		c[i][0] = 0;
	for(j=0;j<=n;j++)
		c[0][j] = 0;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			O++;
			if(x[i] == y[j])
				c[i][j] = c[i-1][j-1]+1, b[i][j] = '@';
			else if(c[i-1][j]>=c[i][j-1])
				c[i][j] = c[i-1][j], b[i][j] = '#';
			else c[i][j] = c[i][j-1],  b[i][j] = '$';
		}
}

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


int main()
{
	
	char x[200];
	char y[200];
	cin>>x;
	cin>>y;
	
	len = LCS(x,y,strlen(x)-1,strlen(y)-1);
	
	cout<<O<<endl;

	for(int i=1;i<=len;i++)
		cout<<k[i];
	cout<<endl;

	/*
	LCS1(x,y,7,6);
	print(b,x,7,6);
	cout<<c[7][6];
		cout<<O<<endl;
		*/
}