sublist.cpp

常用算法与数据结构原代码

#include <iostream.h>
#include <string.h>
#define N 100
int c[N][N];

int get_len(char *a,char *b)
{
	int i,j;
	int m=strlen(a);
	int n=strlen(b);
	for (i=0;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++)
			if (a[i-1]==b[j-1])
				c[i][j]=c[i-1][j-1]+1;
			else
				if (c[i-1][j]>=c[i][j-1])
					c[i][j]=c[i-1][j];
				else
					c[i][j]=c[i][j-1];
	return c[m][n];
}

void build_s(char s[],char *a,char *b,int clen)
{
	int k=clen,i,j,alen=strlen(a),blen=strlen(b);
	s[k]='\0';
	i=alen;
	j=blen;
	while (k>0)
		if (c[i][j]==c[i-1][j])
			i--;
		else
			if (c[i][j]==c[i][j-1])
				j--;
			else
			{
				s[--k]=a[i-1];
				i--;
				j--;
			}
}

void main()
{
	char a[]="ABBCAB";
	char b[]="ABCADAB";
	int n;
	n=get_len(a,b);
	char s[100];
	build_s(s,a,b,n);
	cout<<s<<endl;
}