2799526_ac_0ms_120k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 61 行

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

char a[101][31], b[101][31];
int na, nb, n;
int dp[101][101];
int ans[101];

void lcs()
{
	int i, j;

	memset(dp,0,sizeof(dp));
	for(i = 1; i <= na; i++)
		for(j = 1; j <= nb; j++)
			if(strcmp(a[i-1],b[j-1])==0)
				dp[i][j] = dp[i-1][j-1]+1;
			else
				dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
	n = 0;
	i = na;j = nb;
	while(dp[i][j])
	{
		if(strcmp(a[i-1],b[j-1])==0)
		{
			ans[n++] = i-1;
			i--,j--;
		}
		else
			if(dp[i-1][j]>dp[i][j-1])
				i--;
			else
				j--;
	}
	for(i = n-1; i >= 0; i--)
		printf("%s ",a[ans[i]]);
	printf("\n");
}

int main()
{
	while(scanf("%s",a[0])==1)
	{
		na = 1;
		while(scanf("%s",a[na])==1)
		{
			if(a[na][0]=='#')
				break;
			na++;
		}
		nb = 0;
		while(scanf("%s",b[nb])==1)
		{
			if(b[nb][0]=='#')
				break;
			nb++;
		}
		lcs();
	}
	return 0;
}