POJ. 2192 Zipper

1.Problem
http://poj.org/problem?id=2192

2.Idea
dp[i][j]: true if suffix i+j of C can be made from suffix i of A + suffix j of B, otherwize false.

3.Source

 int t, n, m;  
 string a, b, c;  
 bool dp[202][202];  
 int main()  
 {  
      cin >> t;  
      for (int T = 1; T <= t; T++) {  
           cin >> a >> b >> c;  
           n = a.size();  
           m = b.size();  
           memset(dp, 0, sizeof dp);  
           dp[0][0] = true;  
           for (int i = 0; i <= n; i++) {  
                for (int j = 0; j <= m; j++) {  
                     if (i - 1 >= 0 && a[i - 1] == c[i + j - 1] && dp[i - 1][j]) dp[i][j] = true;  
                     if (j - 1 >= 0 && b[j - 1] == c[i + j - 1] && dp[i][j - 1]) dp[i][j] = true;  
                }  
           }  
           if (dp[n][m]) cout << "Data set " << T << ": yes" << endl;  
           else cout << "Data set " << T << ": no" << endl;  
      }  
      return 0;  
 }