题意：给出两串，两串顺序不变看能否组成第三个串。
此题深搜和DP都能解决：
深搜的话需要几个强有力剪枝条件
1、 第三个串最后一个字符要么是串1的最后一个字符，要么是串2的最后一个字符
2、 按照串1的顺序对串3进行搜索，若不匹配则该字符必是串2的下一个字符。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char first[202],second[202],third[402],Left[401];
int sign[402];
bool flag;
int check()
{int i,count=0;int k=strlen(third);for(i=0;i<k;i++)if(!sign[i]) Left[count++]=third[i];Left[count]='\0';if(strcmp(Left,second)==0) return 1;return 0;
}
int dfs(int f,int s,int t)
{if(f>=strlen(first)){if(check()) flag=true;return 0;}if(flag) return 0;if(first[f]==third[s]){sign[s]=1;if(s<strlen(third)) dfs(f+1,s+1,t);sign[s]=0;}else{if(third[s]!=second[t]) return 0;//剪枝2}if(!flag && s<strlen(third)) dfs(f,s+1,t+1);return 0;
}
int main()
{int len1,len2,len3,Case,count=0;scanf("%d",&Case);while(Case--){count++;flag=false;scanf("%s %s %s",first,second,third);memset(sign,0,sizeof(sign));len1=strlen(first);len2=strlen(second);len3=strlen(third);if(len1+len2!=len3){printf("Data set %d: no\n",count);continue;}if(third[len3-1]!=first[len1-1] && third[len3-1]!=second[len2-1])// 剪枝1{printf("Data set %d: no\n",count);continue;}dfs(0,0,0);if(flag) printf("Data set %d: yes\n",count);else printf("Data set %d: no\n",count);}return 0;
}
若用DP来作先定义res[i][j]=1表示串1前i个字符和串2的前j个字符能组成串3的前i+j个字符，res[i][j]=0则不能。
状态转移方程如下：
Res[i][j]= (third[i+j]==first[i] && res[i-1][j]==1) ||(third[i+j]==second[j]&&res[i][j-1]==1)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char first[201],second[201],third[401];
int res[201][201];
int init(int n,int m)
{int i;for(i=1;i<=m;i++)if(second[i]==third[i]) res[0][i]=1;else break;for(i=1;i<=n;i++)if(first[i]==third[i]) res[i][0]=1;else break;return 0;
}
int dp(int n,int m)
{int i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(third[i+j]==first[i] && res[i-1][j]) res[i][j]=1;if(third[i+j]==second[j] && res[i][j-1]) res[i][j]=1;}if(res[n][m]) return 1;return 0;
}
int main()
{int n,len1,len2,count=0;;scanf("%d",&n);while(n--){count++;scanf("%s %s %s",first+1,second+1,third+1);len1=strlen(first+1);len2=strlen(second+1);memset(res,0,sizeof(res));init(len1,len2);if(dp(len1,len2))printf("Data set %d: yes\n",count);elseprintf("Data set %d: no\n",count);}return 0;
}
