2192.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

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

char w1[210],w2[210],w3[410];
bool ans[210][210];


int main()
{
	int i,j,cas,n,m,k;
	
	scanf( "%d", &cas );
	
	for( k=1; k<=cas; k++ )
	{
		scanf( "%s %s %s", w1+1, w2+1, w3+1 );
		n = strlen( w1+1 );
		m = strlen( w2+1 );
		
		for( i=0; i<=n; i++ )
		for( j=0; j<=m; j++ )
			ans[i][j] = false;

		ans[0][0] = true;

		for( i=0; i<=n; i++ )
		for( j=0; j<=m; j++ )
		if( i || j )
		{
			if( i && ans[i-1][j] && w1[i] == w3[i+j] )
				ans[i][j] = true;
			else if( j && ans[i][j-1] && w2[j] == w3[i+j] )
				ans[i][j] = true;
		}

		printf( "Data set %d: ", k );

		if( ans[n][m] )
			printf( "yes\n" );
		else printf( "no\n" );
	}

	return 0;
}