Strings of Eternity

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定两个仅由小写英文字母组成的非空字符串 $s$ 和 $t$。

请判断满足下列条件的非负整数 $i$ 是否只有有限个；若是，请求出满足条件的最大 $i$：

• 存在某个非负整数 $j$，使得把 $t$ 连续连接 $i$ 次得到的字符串，是把 $s$ 连续连接 $j$ 次得到的字符串的子串。

字符串连接 $0$ 次得到空字符串，空字符串是任意字符串的子串，因此 $i=0$ 一定满足条件。

输入格式

第一行包含字符串 $s$。

第二行包含字符串 $t$。

输出格式

如果满足条件的 $i$ 只有有限个，输出最大的 $i$；如果有无穷多个满足条件的 $i$，输出 $-1$。

样例输入 1

abcabab
ab

样例输出 1

3

样例输入 2

aa
aaaaaaa

样例输出 2

-1

样例输入 3

aba
baaab

样例输出 3

0

数据范围

对于所有数据，$1\le \lvert s\rvert,\lvert t\rvert\le 5\times 10^5$，且两个字符串均只包含小写英文字母。