← 返回比赛

已结束 GESP欢乐赛 #14

← 上一题下一题 →

A1540 | $字符串增生$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一天，Yuilice的好朋友Ruby给他出了一道字符串题目，Yuilice希望你可以帮他写一道程序，在1秒内快速计算出答案。 题目描述如下: 给出两个整数$N,M(1 \leq N,M \leq 25)$，同时输入长度为$N,M$的字符串$A,B$。 你可以对字符串$A$无限制次数的进行"增生"操作，"增生"操作效果为将当前的字符串$A$复制一份，黏贴连接在字符串$A$的末尾。 例: $A = Yuilice$,那么进行增生操作的效果如下。 字符串A操作次数Yuilice0YuiliceYuilice1YuiliceYuiliceYuiliceYuilice2 Ruby希望知道，字符串$A$最少需要经过多少次增生，字符串B才能在字符串$A$中出现？输出最少次数。如果出现不了，那么输出-1。

输入格式

输入第一行为一个正整数$t(1 \leq t \leq 10^4)$，代表接下来会有$t$组样例进行测试。 随后$t$组样例中，第一行输入两个整数$N,M$,代表字符串的长度。接下来两行分别输入字符串$A,B$。

输出格式

输出一个整数代表最少增生次数。

输入输出样例

输入 #1

5
7 4
Yuilice
eYui
1 4
c
cccc
4 3
babb
bbb
7 7
Yuilice
Yuilice
3 5
bc
bcbcb

输出 #1

C++ 编辑器

输入

输出