首页 > 试题广场 >

小猿的纸条

[编程题]小猿的纸条
  • 热度指数:345 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小猿有两张分别写着字符串s1、s2的纸条,字符串由大小写字母组成。小猿会进行n次操作,每次操作时小猿会选择其中一张纸条,把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序,从左到右将收到的n张纸条拼接成一张新的纸条。
已知字符串s1、s2,求是否存在一种方案使新纸条上的字符串与s3相同、且满足n<=K。

输入描述:
第一行输入T(T ≤ 20),表示输入T组数据。
接下来T行,每行按顺序输入字符串s1、s2、s3和正整数K(K ≤ 50),用空格分开。
字符串s1、s2长度不超过200,s3长度不超过400。


输出描述:
输出T行,每行输出对应组数据方案是否存在。存在输出1,不存在输出0。
示例1

输入

1
ac bb abbc 3

输出

1

说明

方案为:1.小猿从第一张纸条撕下a给你。2.小猿将第二张纸条bb给你。3.小猿将第一张纸条剩下的c给你。你收到3张纸条,按顺序拼成abbc,符合条件。