lcs.c

本程序计算两个序列的最长公共子序列LCS

/****************************************************
LCS.c    2008_0508_1352    
*****************************************************/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXSIZE  100

void lcslength(char x[], char y[], int m, int n, int c[][MAXSIZE], char b[][MAXSIZE])
{
	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++)
		{
			if (x[i]==y[j])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]='t';
			}
			else if (c[i-1][j] >= c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]='u';
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]='l';
			}
		}
	}
	
	return;
}

void prntlcs(char b[][MAXSIZE], char x[], int i, int j)
{
	if (i==0 || j==0)
	{
		return;
	}

	if (b[i][j]=='t')
	{
		prntlcs(b, x, i-1, j-1);
		printf("%c", x[i]);
	}
	else if (b[i][i]=='u')
	{
		prntlcs(b, x, i-1, j);
	}
	else
	{
        prntlcs(b, x, i, j-1);
	}	
	
	return;
}

void input(char x[], char y[], int *m, int *n)
{
	int i;
	
/*  *x="BDCABA";
	y="ABCBDAB";
*/
	printf("Please input the x[]:");
	scanf("%s", x);

	printf("Please input the y[]:");
	scanf("%s", y);

	*m=strlen(x);
	*n=strlen(y);

	for (i=*m+1; i>0; i--)
	{
		x[i]=x[i-1];
	}

	for (i=*n+1; i>0; i--)
	{
		y[i]=y[i-1];
	}

	printf("*******************************************\n");
/*	printf("m=%d n=%d\n", m, n);
	printf("%c\n",x[1]);
	printf("%c\n",x[1]);
*/
}
void main()
{
    char x[MAXSIZE];
	char y[MAXSIZE];
	char b[MAXSIZE][MAXSIZE];
	int c[MAXSIZE][MAXSIZE];
	int m, n;
	int *pm, *pn;	
	//int i,j;
	//int k;

	m=0;
	n=0;
	pm=&m;
	pn=&n;

	input(x, y, pm, pn);
	
	//printf("m=%d n=%d\n", m, n);

	lcslength(x, y, m, n, c, b);

	printf("The LCS is:\n");
	prntlcs(b, x, m, n);
	printf("\n");

/*	for (k=1; k<m+1; k++)
	{
	    printf("%d->%c\n", k, x[k]);
	}
	for (k=1; k<m+1; k++)
	{
	    printf("%d->%c\n", k, y[k]);
	}
*/
	system("pause");

}