随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 #define MaxSize 205
 5 char str1[MaxSize],str2[MaxSize],str[MaxSize<<1];
 6 int mark[MaxSize<<1][MaxSize<<1];//此题用mark标记一下非常关键!!否则超时
 7 int n,len1,len2,len;
 8 bool isOK;
 9 
10 void dfs(int num1,int last_pos,int num2){
11     //一号字符串当前需要匹配的位置,上一次一号字符串匹配的位置,二号字符串当前需要匹配的位置
12     int i,j,k;
13     if(isOK)    
14         return;
15     if(mark[num1][num2])
16         return;
17     mark[num1][num2]=1;
18     if(num1>len1){//当一号字符串匹配完毕!
19         for(j=last_pos+1,k=num2;j<=len;j++,k++)
20             if(str[j]!=str2[k])    return;
21         isOK=true;    return;
22     }
23     for(i=last_pos+1;i<=len;i++){
24         if(str[i]==str1[num1]){
25             for(j=last_pos+1,k=num2;j<i;j++,k++)
26                 if(str[j]!=str2[k])    return;
27             dfs(num1+1,i,k);    
28         }
29     }
30     
31 }
32 
33 int main(){
34     //freopen("in.txt","r",stdin);
35     int i;
36     scanf("%d",&n);
37     getchar();
38     for(i=1;i<=n;i++){
39         scanf("%s %s %s",str1+1,str2+1,str+1);
40         str1[0]=str2[0]=str[0]='0';
41         len1=strlen(str1)-1;
42         len2=strlen(str2)-1;
43         len=len1+len2;
44         isOK=false;
45         memset(mark,0,sizeof(mark));
46         dfs(1,0,1);
47         printf("Data set %d: ",i);
48         if(isOK)
49             puts("yes");
50         else
51             puts("no");
52 
53     }
54     return 0;
55 }
56 
posted on 2012-07-10 19:07 Leo.W 阅读(51) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理