AT_abc135_f [ABC135F] Strings of Eternity

给定两个由小写英文字母组成的字符串 $s$ 和 $t$。请判断满足下述条件的非负整数 $i$ 的个数是否有限，如果有限，请求出满足条件的 $i$ 的最大值。 - 存在某个非负整数 $j$，使得将 $t$ 连续连接 $i$ 次得到的字符串，是将 $s$ 连续连接 $j$ 次得到的字符串的子串。

输入以以下格式从标准输入读入。 > $s$ $t$

如果满足条件的非负整数 $i$ 的个数有限，则输出满足条件的 $i$ 的最大值；如果有无穷多个满足条件的 $i$，则输出 $-1$。

## 注释 - 若字符串 $a$ 是字符串 $b$ 的子串，意味着存在整数 $x$（$0 \leq x \leq |b| - |a|$），对于任意整数 $y$（$1 \leq y \leq |a|$），都有 $a_y = b_{x+y}$。 - 对于任意字符串，将其连接 $0$ 次得到的字符串视为空字符串。根据上述定义，空字符串是任意字符串的子串。因此，对于任意两个字符串 $s$ 和 $t$，$i = 0$ 一定满足题目中的条件。 ## 约束 - $1 \leq |s| \leq 5 \times 10^5$ - $1 \leq |t| \leq 5 \times 10^5$ - $s$ 和 $t$ 均由小写英文字母组成。 ## 样例解释 1 将 $t$ 连续连接 $3$ 次得到的字符串 `ababab`，是将 $s$ 连续连接 $2$ 次得到的字符串 `abcabababcabab` 的子串，因此 $i = 3$ 满足条件。而将 $t$ 连续连接 $4$ 次得到的字符串 `abababab`，无论将 $s$ 连接多少次，都不会作为其子串出现，因此 $i = 4$ 不满足条件。同理，任意大于等于 $5$ 的整数也不满足条件。因此，满足条件的非负整数 $i$ 的个数是有限的，其最大值为 $3$。 ## 样例解释 2 对于任意非负整数 $i$，将 $t$ 连续连接 $i$ 次得到的字符串，都是将 $s$ 连续连接 $4i$ 次得到的字符串的子串。因此，满足条件的非负整数 $i$ 有无穷多个。 ## 样例解释 3 如注释所述，$i = 0$ 一定满足条件。 由 ChatGPT 4.1 翻译