(字符串模式匹配4.7.10)POJ 2192 Zipper(判断第3个字符串能否有前两个字符串组成)

 
/* 
 * POJ_2192.cpp 
 * 
 *  Created on: 2013年10月28日 
 *      Author: Administrator 
 */  
  
  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
  
using namespace std;  
  
const int maxn = 210;  
int main(){  
    int t;  
    scanf("%d",&t);  
    int  counter = 1;  
    char str1[maxn],str2[maxn],str3[maxn*2];//注意,str3所取的长度应该是str1与str2之和  
    bool can[maxn][maxn];  
  
  
    while(t--){  
        memset(can,0,sizeof(can));  
        can[0][0] = 1;  
  
        scanf("%s%s%s",str1,str2,str3);  
        int k1 = strlen(str1);  
        int k2 = strlen(str2);  
  
        int i,j;  
        for(i = 0 ; i <= k1 ; ++i){  
            for(j = 0 ; j <= k2 ; ++j){  
                if(i >= 1 && str3[i+j-1] == str1[i-1] && can[i-1][j] == 1){//当c[i+j-1] == a[i-1]时,需要看一下c[i+j-1]是否能由a[i-2]和b[j-1]组成  
                    can[i][j] = 1;  
                }else if(j >= 1 && str3[i+j-1] == str2[j-1] &&  can[i][j-1] == 1){  
                    can[i][j] = 1;  
                }  
            }  
        }  
  
        if(can[k1][k2]){  
            printf("Data set %d: yes\n",counter++);  
        }else{  
            printf("Data set %d: no\n",counter++);  
        }  
    }  
  
    return 0;  
}  
 

补充：软件开发 , C++ ,

上一个：UVA 11401 - Triangle Counting
下一个：POJ 1408 Fishnet 两线段交点坐标