F - 字符串的永恒

得分：$600$ 分

问题描述

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

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

注意事项

• 字符串 $a$ 是字符串 $b$ 的子串，当且仅当存在一个整数 $x$ $(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$ 由小写英文字母组成。

输入

从标准输入中按以下格式给出输入：

$s$

$t$

输出

如果满足以下条件的非负整数 $i$ 的数量是有限的，请输出满足条件的最大值；如果是无限的，请输出 -1。

abcabab
ab

3

三个 $t$ 的串联，ababab，是两个 $s$ 的串联，abcabababcabab，的子串，所以 $i = 3$ 满足条件。

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

同样地，大于 $4$ 的任何整数都不满足条件。因此，满足条件的非负整数 $i$ 的数量是有限的，且满足条件的最大值是 $3$。

aa
aaaaaaa

-1

对于任意非负整数 $i$，$i$ 个 $t$ 的串联是 $4i$ 个 $s$ 的串联的子串。因此，存在无穷多个满足条件的非负整数 $i$。

aba
baaab

0

正如注意事项中所述，$i = 0$ 无论如何都满足条件。