题目链接:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2192
采用动态规划的方法,类似LCS
f(i,j)表示是s1前i个字符,s2前j个字符能否组成s3前i + j个字符
f(0,0) = 0;
f(i,j) = (f(i - 1,j) && s1[i - 1] == s3[i + j - 1] && i >= 1) || f(i,j - 1) && s2[j - 1] == s3[i + j + 1] && j >= 1);
#include <iostream>
using namespace std;
char s1[202],s2[202],s3[406];
bool dp[202][202];
int main(){
int casenum;
//FILE *fp = fopen("data.txt","r");
//fscanf(fp,"%d",&casenum);
scanf("%d",&casenum);
int i,j,k;
int len1,len2;
for(k = 1;k <= casenum;k++){
//fscanf(fp,"%s%s%s",s1,s2,s3);
scanf("%s%s%s",s1,s2,s3);
memset(dp,0,sizeof(dp));
dp[0][0] = true;
len1 = strlen(s1);
len2 = strlen(s2);
for(i = 0;i <= len1;i++)
for(j = 0;j <= len2;j++)
if((dp[i - 1][j] && s1[i - 1] == s3[i + j - 1] && i >= 1) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1] && j >= 1) == true)
dp[i][j] = true;
if(dp[len1][len2])
printf("Data set %d: yes/n",k);
else
printf("Data set %d: no/n",k);
}
return 0;
}