#include#include int flag; int len1,len2,len3; const int maxn=205; char str1[maxn]; char str2[maxn]; char str3[maxn*2]; int dp[maxn][maxn]; void dfs(int x1,int x2,int x3){ if(x3>=len3){ flag=1;return; } if(flag==1)return; if(dp[x1][x2])return; if(str1[x1]==str3[x3]){ dfs(x1+1,x2,x3+1); } if(str2[x2]==str3[x3]){ dfs(x1,x2+1,x3+1); } dp[x1][x2]=1; } int main(){ int n; int cas=1; scanf("%d",&n); while(n--){ memset(str1,'\0',sizeof(str1)); memset(str1,'\0',sizeof(str2)); memset(str1,'\0',sizeof(str3)); memset(dp,0,sizeof(dp)); scanf("%s%s%s",&str1,&str2,&str3); len1=strlen(str1); len2=strlen(str2); len3=strlen(str3); if(len1+len2!=len3){ printf("Case %d: no\n",cas++); continue; } else{ flag=0; dfs(0,0,0); if(flag==0)printf("Case %d: no\n",cas++); else printf("Case %d: yes\n",cas++); } } return 0; }
DP：
#include#include int main() { int n, dp[201][201], i, j, la, lb, C = 0; char a[201], b[201], c[402]; scanf("%d", &n); while (n--) { scanf("%s%s%s", a, b, c); memset(dp, 0, sizeof(dp)); la = strlen(a); lb = strlen(b); for (i = 0; i < la; i++) { if (a[i] == c[i]) dp[i + 1][0] = 1; else break; } for (i = 0; i < lb; i++) { if (b[i] == c[i]) dp[0][i + 1] = 1; else break; } for (i = 1; i <= la; i++) for (j = 1; j <= lb; j++) if ((dp[i - 1][j] && a[i - 1] == c[i + j - 1]) || (dp[i][j - 1] && b[j - 1] == c[i + j - 1])) dp[i][j] = 1; printf("Case %d: ", ++C); puts(dp[la][lb] "yes" : "no"); } return 0; }