题目链接：http://poj.org/problem?id=2192
题意：给3个字符串，问第3个字符串是不是由前两个拼插构成的。
对前两个字符串从左到右dfs即可，注意dfs前判断掉所有的不可能的情况。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 20 const int maxn = 1010; 21 char a[maxn], b[maxn], c[maxn]; 22 int n, m, o; 23 bool vis[256]; 24 25 26 bool dfs(int x, int y, int z) { 27 if(x == n && y == m) return 1; 28 if(x < n && c[z] == a[x]) { 29 if(dfs(x+1, y, z+1)) return 1; 30 } 31 if(y < m && c[z] == b[y]) { 32 if(dfs(x, y+1, z+1)) return 1; 33 } 34 return 0; 35 } 36 37 int main() { 38 // freopen("in", "r", stdin); 39 int T, _ = 1; 40 scanf("%d", &T); 41 while(T--) { 42 memset(vis, 0, sizeof(vis)); 43 scanf("%s %s %s", a, b, c); 44 n = strlen(a); m = strlen(b); o = strlen(c); 45 for(int i = 0; a[i]; i++) vis[a[i]] = 1; 46 for(int i = 0; b[i]; i++) vis[b[i]] = 1; 47 printf("Data set %d: ", _++); 48 if(o != n + m) { 49 puts("no"); 50 continue; 51 } 52 if(a[0] != c[0] && b[0] != c[0]) { 53 puts("no"); 54 continue; 55 } 56 if(a[n-1] != c[o-1] && b[m-1] != c[o-1]) { 57 puts("no"); 58 continue; 59 } 60 bool flag = 0; 61 for(int i = 0; c[i]; i++) { 62 if(!vis[c[i]]) { 63 flag = 1; 64 break; 65 } 66 } 67 if(flag) { 68 puts("no"); 69 continue; 70 } 71 flag = dfs(0, 0, 0); 72 if(flag) puts("yes"); 73 else puts("no"); 74 } 75 return 0; 76 }