(字符串模式匹配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;}