#include<stdio.h>
#include<string.h>
#define N 110

int p[N][N];

int fun(char obj1[][40], char obj2[][40], int k1, int k2)
{
	int i, j;
	int c[N][N];
	
	for (i=1; i<k1; i++)
		c[i][0] = 0;
	for (i=1; i<k2; i++)
		c[0][i] = 0;
	c[0][0] = 0;
	
	for (i=1; i<k1; i++)
		for (j=1; j<k2; j++)
		{
			if (!strcmp(obj1[i], obj2[j]))
			{
				c[i][j] = c[i-1][j-1] + 1;
				p[i][j] = 1;
			}
			else if (c[i-1][j] > c[i][j-1])
			{
				c[i][j] = c[i-1][j];
				p[i][j] = 2;
			}
			else
			{
				c[i][j] = c[i][j-1];
				p[i][j] = 3;
			}
		}
		
		return c[k1-1][k2-1]; 
}

void output(char obj1[][40], int k1, int k2)
{
	int i;
	int a[N];
	
	i = 0;
	--k1; 
	--k2;
	while (k1>=1 && k2>=1)
	{
		if (p[k1][k2] == 1)
		{
			a[i++] = k1;
			k1--; k2--;
		}
		else if (p[k1][k2] == 2)
		{
			k1--;
		}
		else
		{
			k2--;
		}
	}
	
	--i;
	while (i)
	{
		printf("%s ", obj1[a[i--]]);
	}
	printf("%s\n\n", obj1[a[i]]);
	
	return ;
}

int main()
{
	char obj1[N][40], obj2[N][40];
	int k1, k2;
	
	while (fscanf(stdin, "%s", obj1[1]) != EOF)
	{
		k1 = 2;
		fscanf(stdin, "%s", obj1[k1++]);
		while (strcmp(obj1[k1-1], "#"))
		{
			fscanf(stdin, "%s", obj1[k1++]);
		}
		--k1;
		
		k2 = 1;
		fscanf(stdin, "%s", obj2[k2++]);
		while (strcmp(obj2[k2-1], "#"))
		{
			fscanf(stdin, "%s", obj2[k2++]);
		}
		--k2;
		
		fun(obj1, obj2, k1, k2);
		output(obj1, k1, k2);
	}
	return 0;
}

• Re:我只想说太坑爹了！付AC代码！ (38) jli114 2012-11-09 18:27:54