小猿有两张分别写着字符串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 ac bb abbc 3
1
方案为:1.小猿从第一张纸条撕下a给你。2.小猿将第二张纸条bb给你。3.小猿将第一张纸条剩下的c给你。你收到3张纸条,按顺序拼成abbc,符合条件。
暂无题解