「Count The Repetitions」 计算重复

定义 $conn(s,n)$ 为 n 个字符串 s 首尾相接形成的字符串，例如：

称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。

例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。

给定两个字符串 $s_1$ 和 $s_2$，以及两个整数 $n_1$ 和 $n_2$，求一个最大的整数 m，满足$conn(conn(s_2,n_2 ),m)$ 能由 $conn(s_1,n_1)$ 生成。

输入格式

输入包含多组测试数据。

每组数据由2行组成，第一行包含$s_2,n_2$，第二行包含$s_1,n_1$。

输出格式

对于每组数据输出一行表示答案m。

数据范围

$s_1$ 和 $s_2$ 长度不超过100，$n_1$ 和 $n_2$ 不大于 $10^6$。

输入样例：

ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20

输出样例：

2
1
4
7
12

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解