YTU 2896: J--Zipper
2896: J--Zipper
时间限制: 1 Sec 内存限制: 128 MB
提交: 29 解决: 15
题目描述
Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":
String A: cat
String B: tree
String C: catrtee
Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
输入
The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.
For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two
strings will have lengths between 1 and 200 characters, inclusive.
输出
For each data set, print:
Data set n: yes
if the third string can be formed from the first two, or
Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.
样例输入
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
样例输出
Data set 1: yes
Data set 2: yes
Data set 3: no
你 离 开 了 , 我 的 世 界 里 只 剩 下 雨 。 。 。
#include<stdio.h>
#include<string.h>
#define MAX 201
int opt[MAX][MAX];
int main()
{
int n;
int cnt=0;
char str1[MAX],str2[MAX],str3[MAX*2];
int len_str1,len_str2,len_str3;
int i,j;
scanf("%d",&n);
while(n--)
{
cnt++;
scanf("%s %s %s",str1,str2,str3);
len_str1=strlen(str1);
len_str2=strlen(str2);
len_str3=strlen(str3);
if(len_str1+len_str2!=len_str3)
{
printf("Data set %d: no\n",cnt);
continue;
}
memset(opt,0,sizeof(opt));
opt[0][0]=1;
for(i=1; i<=len_str1; i++)
{
if(opt[i-1][0]==1&&str1[i-1]==str3[i-1]) opt[i][0]=1;
else break;
}
for(j=1; j<=len_str2; j++)
{
if(opt[0][j-1]==1&&str2[j-1]==str3[j-1]) opt[0][j]=1;
else break;
}
for(i=1; i<=len_str1; i++)
{
for(j=1; j<=len_str2; j++)
{
if((opt[i][j-1]==1&&str2[j-1]==str3[i+j-1])||(opt[i-1][j]==1&&str1[i-1]==str3[i+j-1]))
opt[i][j]=1;
}
}
if(opt[len_str1][len_str2]) printf("Data set %d: yes\n",cnt);
else printf("Data set %d: no\n",cnt);
}
return 0;
}
#include<string.h>
#define MAX 201
int opt[MAX][MAX];
int main()
{
int n;
int cnt=0;
char str1[MAX],str2[MAX],str3[MAX*2];
int len_str1,len_str2,len_str3;
int i,j;
scanf("%d",&n);
while(n--)
{
cnt++;
scanf("%s %s %s",str1,str2,str3);
len_str1=strlen(str1);
len_str2=strlen(str2);
len_str3=strlen(str3);
if(len_str1+len_str2!=len_str3)
{
printf("Data set %d: no\n",cnt);
continue;
}
memset(opt,0,sizeof(opt));
opt[0][0]=1;
for(i=1; i<=len_str1; i++)
{
if(opt[i-1][0]==1&&str1[i-1]==str3[i-1]) opt[i][0]=1;
else break;
}
for(j=1; j<=len_str2; j++)
{
if(opt[0][j-1]==1&&str2[j-1]==str3[j-1]) opt[0][j]=1;
else break;
}
for(i=1; i<=len_str1; i++)
{
for(j=1; j<=len_str2; j++)
{
if((opt[i][j-1]==1&&str2[j-1]==str3[i+j-1])||(opt[i-1][j]==1&&str1[i-1]==str3[i+j-1]))
opt[i][j]=1;
}
}
if(opt[len_str1][len_str2]) printf("Data set %d: yes\n",cnt);
else printf("Data set %d: no\n",cnt);
}
return 0;
}
最新文章
- spring aop配置出错
- ButterKnife 8.2.1 大圣归来
- Material Design Lite,简洁惊艳的前端工具箱。
- linux内存分配
- 同步文本框内容的JS代码
- CC2540 USB Dongle 使用说明
- Linux 硬盘分区
- WMI远程访问问题解决方法
- 使用aspose.word两句代码将word转换为pdf
- Cocos2D创建项目
- DLL模块:C++在VS下创建、调用dll
- android开发隐藏了actionbar仍然短暂闪现的解决方法
- RedGate 工具SQLTEST 1.0.15.1
- 【Android Developers Training】 58. 缓存位图
- js代码执行顺序问题
- 【原创】公司各个阶段 CTO 需要做什么?(上篇)
- 记录一次群答问:jmeter正则提取器提取一个及多个值
- 【异常】Servlet.service() for servlet [springMvc] in context with path [/orderdishessystem] threw exception [Handler processing failed; nested exception is java.lang.NoClassDefFoundError: net/sf/ezmorph/M
- Maven(十二)Maven 依赖详解
- Mac端解决(含修改8.0.13版的密码):Can&#39;t connect to local MySQL server through socket &#39;/tmp/mysql.sock&#39; (2)
热门文章
- 在WinForm里嵌入WPF模拟公交运行状态
- python模块以及导入出现ImportError: No module named ‘xxx‘问题
- HDU 5487 Difference of Languages
- 【Ts 1】 maven初识
- iOS-runtime-根据类名推送到任意控制器,且实现属性传值
- HDU1423 最长公共上升子序列LCIS
- 【模拟】2017 Multi-University Training Contest 1 The Battle of Chibi
- idea-自定义Java模板文件
- 理解 mysql行锁和表锁
- Java模拟斗地主(实现大小排序)