题目描述

Given are two strings $s$ and $t$ consisting of lowercase English letters. Determine if the number of non-negative integers $i$ satisfying the following condition is finite, and find the maximum value of such $i$ if the number is finite.

• There exists a non-negative integer $j$ such that the concatenation of $i$ copies of $t$ is a substring of the concatenation of $j$ copies of $s$.

给出两个由小写英文字母组成的字符串 $s$ 和 $t$ 。请判断满足以下条件的非负整数 $i$ 的个数是否有限，如果是有限的，求这个 $i$ 的最大值。

• 存在一个非负整数 $j$ ，使得 $i$ 份数 $t$ 的连接是 $j$ 份数 $s$ 的连接的子串。

输入格式

输入内容按以下格式标准输入：

$s$
$t$

输出格式

如果满足以下条件的非负整数 $i$ 的个数是有限的，则打印该 $i$ 的最大值；如果个数是无限的，则打印 -1。

样例 #1

样例输入 #1

abcabab
ab

样例输出 #1

3

样例 #2

样例输入 #2

aa
aaaaaaa

样例输出 #2

-1

样例 #3

样例输入 #3

aba
baaab

样例输出 #3

0

说明

• 当且仅当存在整数 $x$ 时，字符串 $a$ 是另一个字符串 $b$ 的子串。 $(0 \leq x \leq |b| - |a|)$ 这样的整数，对于任意 $y$ $(1 \leq y \leq |a|)$ 时， $a_y = b_{x+y}$ 成立。

• 我们假设任意字符串的零副本的连接就是空字符串。根据上述定义，空字符串是任意字符串的子串。因此，对于任意两个字符串 $s$ 和 $t$ , $i = 0$ 都满足问题陈述中的条件。

数据规模与约定

• $1 \leq |s| \leq 5 \times 10^5$
• $1 \leq |t| \leq 5 \times 10^5$
• $s$ 和 $t$ 由小写英文字母组成。

样例 $1$ 解释

三份 $t$ ababab 的连接是两份 $s$ abcabababcabab 的连接的子串，因此 $i = 3$ 满足条件。

另一方面， $t$ 的四个副本 "abababab`"的连接不是 $s$ 的任何数量副本的连接的子串，所以 $i = 4$ 不满足条件。

同样，任何大于 $4$ 的整数也不满足条件。因此，满足条件的非负整数 $i$ 的个数是有限的，而这样的 $i$ 的最大值是 $3$ 。

样例 $2$ 解释

对于任意一个非负整数 $i$ ， $t$ 的 $i$ 份数的连接是 $s$ 的 $4i$ 份数的连接的子串。因此，满足条件的非负整数 $i$ 有无限多个。

样例 $3$ 解释

如注释所述， $i = 0$ 始终满足条件。